求有权无向图的DFS算法
留个邮箱，我发给你
C++写的，动态规划算法， 注释写得很清楚，已发你邮箱，我邮箱zzkongfu@163.com
深度优先遍历类似于树的先序遍历，俗称一条路走到黑，然后再考虑回溯的问题，回溯到最近访问的顶点并看它是否还有相邻顶点未访问，若无继续往前回溯。我下面写写核心伪代码，其他诸如图的类型定义、还有你要对每个结点做的具体操作（我在代码中用visit()函数来代替了，具体做啥操作根据题目来）我就不写了。
bool visited[MSX_VERTEX_NUM]; //标记访问数组
void DFS_Traverse(Grath G) //对图G进行DFS
{
for(v=0;v<G.vexnum;++v)
{
visited[v]=false; //初始化已访问标记数据
}
for(v=0;v<G.vexnum;++v) //假设从v=0开始遍历
{
if(!visited[v])
DFS(G,v);
}
}
void DFS(Graph G,int v) //从顶点v出发，用递归的思想，深度优先遍历
{
visit(v); //这里的visit()就是对顶点v的具体操作，题目是啥就自己写啥
visited[v]=true; //标记已访问
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
//从最近结点开始，依次找相邻结点
{
if(!visited[w]) //w为还未访问的相邻结点
{
DFS(G,w);
}
}
}
连通分图有哪些计算方法?
在DFS遍历过程中，从一个顶点出发，通过该顶点遍历到的所有顶点属于同一连通分量，这些遍历到的顶点做好标记，表示已经被访问，直到所有顶点均被标记。具体实现过程可以参考中的方法，通过一个变量id记录每个顶点具体属于某个连通分量。在图论中，连通图基于连通的概念。在一个无向图G中，若从顶点i到顶点j...
acmdfs判断无向图是否有环
第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。如果最后还有未删除顶点，则存在环，否则没有环。n算法分析：由于有m条边，n个顶点。i)如果m>=n，则根据图论知识可直接判断存在环路。（证明：如果没有环路，则该图必然是k棵树 k>=1。根据树的性质，边的数目m = n-...
图1给出一个无向图。从顶点1出发,DFS遍历的输出序列是( )。
一种DFS序列是：1-2-4-5-3-6-7 给出的答案中，答案C是正确的。
数据结构-图的简介
还有一些图中，顶点之间的关联并不是完全对称的，举个例子比如说微博，你的粉丝列表里有我，但我的粉丝列表里未必有你，类似于这种单方面关注的，顶点之间的边就有了方向的区分，这种带有方向的图称为 有向图 。因此，综合有向无向、带权重不带权重，交叉来讲，图有带权重有向的、 带权重无向的 ...
对连通图进行一次先深遍历可访问图的全部顶点,对吗
如果是无向的连通图或者有向的强连通图,是对的,对于无向的非连通图就不可能一次遍历访问到所有顶点了,对于有向的非强连通图则有可能对,有可能不对
已知某无向图的邻接矩阵如下,写出从顶点V4出发用DFS、BFS遍历该图的结...
DFS:v4,v1,v0,v3,v2,v7,v6,v5,v10,v8,v9,v11,v12 深度遍历，从V4开始找V4行对应的列为1的顶点，如上图找到了V1，接着继续找V1行对应的列为1的顶点，找到V0，再从V0行找，找到V1，但V1已经访问过了，继续向后找，找到了V3如此循环下去，最后找完了所有的但还有没访问的节点，如上...
用C语言编程判断一个无向图是不是欧拉图?
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图是连通图。一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。可以用邻接矩阵或者邻接表，做一次DFS或者BFS访问各个节点判断入度出度就行。
数据结构选择题,帮忙解释下为什么。谢谢
深度优先算法搜索路径恰恰是一条弧，栈的输出是从最后一个被访问点开始输出，最后一个输出的点是第一个被访问的点。所以是逆的拓扑有序序列 第二题：无向图路径长度是指两个顶点之间弧的条数，如果两顶点路径长度有2条弧，则有3个顶点例如A——B——C；第三题：A：极小连通图是一棵生成树，...
判断无向图是否是一棵树的疑问
首先这是一个无向图，用邻接表存储的顶点是无向图中顶点的2倍， 边自然也是二倍。但是这里为什么判断的时候顶点数没有乘以二而边数乘以二了呢？仔细看DFS深度遍历代码，while中有一个判断该顶点是否已遍历的语句，如果遍历过，则不执行递归，这就是为什么顶点数没有乘以二的原因；再说边数为什么要乘以...
无向图用矩阵幂算法如何求其连通分支数
特别地有A[x][x]=1 此时A[x][y]>0当且仅当x->y有直接连通的边 再考虑A^2=A*A，A^2[x][y]>0当且仅当x->y有长度小于等于2条边的通路 最后，A^n[x][y]>0当且仅当x->y有任意长度的通路（n是节点数目）所以用快速幂求出A^n，然后将A^n作为邻接矩阵，DFS一遍就可以了 ...
第叶增抗： 首先选定图的类别(有向图、无向图),再选定图的存储结构,根据输入的顶点或者边建立图;并把相应的邻接表或者邻接矩阵输出; 根据已有的邻接矩阵或邻接表用递归方法编写深度优先搜索遍历算法,并输出遍历结果; 图的深度遍历原则...
嘉善县19645847664： C或C++遍历一个有权无向图 - ？
第叶增抗： #define M 20#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <graphics.h> typedef struct{ /*x,y坐标的结构体*/ int x; int y; }node; typedef struct{ /*图结构*/ int V[M]; int R[M][M]; int vexnum; node loc[M]; }Graph; void creatgraph(Graph *g...
嘉善县19645847664： 数据结构 -- 关于图的操作?？
第叶增抗： #include ＂datastru.h＂ #include <stdio.h> #include <malloc.h> MGRAPH create_mgraph() {/*建立图的邻接矩阵*/ int i,j,k; MGRAPH mg; mg.kind=2; printf(＂\n\n输入顶点数和边数(用逗号隔开) : ＂); scanf(＂%d,%d＂,&i,&j);fflush(stdin); mg....
嘉善县19645847664： 求一个最优路径算法的思路 - ？
第叶增抗： 同意楼上,最长路径是NPC问题,不存在多项式算法.证明是简单的:1、最长无环路问题的判定版本是“给定有向图D和整数k,问D中是否存在长度大于或等于k的无环路”(这一表述对有权图和无权图...
嘉善县19645847664： 试编写求无向图G的连通分量的算法.要求输出每一连通分量的顶点值.(设图G已用邻接表存储) - ？
第叶增抗： 你肯定还没看懂邻接表,adjvex就是顶点的数组地址,每个顶点都有自己的物理地址,通过数组来存储比较方便操作,不然怎么找到它,你想想.至于前面的算法,我想你看懂了邻接表之后看算法很简单了,这算法没什么技术含量.就是直接利用邻接表的特点
嘉善县19645847664： 考研数据结构无向图的算法,用一维数组表示邻接矩阵,并求各连通分量的顶点集 - ？
第叶增抗： 这个其实很好办的,在有向图的基础上,作如下修改.创建有向图的过程中,用一个数来表示是否相连,可以设置weight为1或0.可以在确定一条弧的两个顶点后,locate其位置后将其的权值定为1或0,1表示相连,0表示不相连.这时候赋值的时候写两句,比如说这样: G->arcs[i][j].adj=weight; G->arcs[j][i].adj=weight; 其中i,j分别表示所在的行与列.G是一个图,arcs是一个邻接矩阵,adj就是权值,weight是具体的值,为1或0.这里写了两遍的语句就是实现了无向图的创建.其他的程序就可以依此进行修改,这个还是比较简单的,好好写吧...
嘉善县19645847664： 数据结构课程设计题目,图的建立以及遍历. - ？
第叶增抗： //图的遍历算法程序 //图的遍历是指按某条搜索路径访问图中每个结点,使得每个结点均被访问一次,而且仅被访问一次.图的遍历有深度遍历算法和广度遍历算法,程序如下: #include <iostream> //#include <malloc.h> #define INFINITY 32767 ...
嘉善县19645847664： 设计算法判断给定的无向图是否存在包含所有结点的简单路径 - ？
第叶增抗： 若用无向图表示高速公路网,其中顶点表示城市,边表示城市之间的高速公路.试设计 一个找路程序,获取两个城市之间的所有简单路径. 基本要求 (1) 输入参数:结点总数,结点的城市编号(4 位长的数字,例如电话区号,长沙 是 0731)...
嘉善县19645847664： 怎样求无向图的桥？
第叶增抗： 首先任选一点为根进行DFS,对于每个结点i,记录dfn[i]-i被第一次访问时的次序,dp[i]-DFS树中从i开始通过前向弧和后向弧所能到达的最小的dfn. dfn很容易记录,对于dp[i],我们采用树型动态规划的方法求出. 第一次访问i:dp[i]=dfn[i] i的儿子...
嘉善县19645847664： acmdfs判断无向图是否有环 - ？
第叶增抗： 如果存在回路,则必存在一个子图,是一个环路.环路中所有顶点的度>=2. n算法:第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一.第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶...
