假设一个连通图采用邻接表作为存储结构，试设计一个算法，判断其中是否存在经过顶点v的回路
从顶点v出发进行深度优先遍历，用d记录走过的路径长度，对每个访问的顶点设置标记为1。若当前访问顶点u，表示vðu存在一条路径，如果顶点u的邻接点w等于v并且d>1，表示顶点u到v有一条边，即构成经过顶点v的回路，如下图所示。 求解问题的算法为： voidCycle(AdjGraph *G,int u,int v,int d,bool &has) 其中，has是布尔值，初始调用时置为false，执行后若为true表示存在经过顶点v的回路，否则表示没有相应的回路。 算法如下： int visited[MAXV]; //全局变量数组 voidCycle(AdjGraph *G,int u,int v,int d,bool &has) { //调用时has置初值false,d为-1 ArcNode*p; int w; visited[u]=1;d++; //置已访问标记 p=G->adjlist[u].firstarc; //p指向顶点u的第一个邻接点 while(p!=NULL) { w=p->adjvex; if(visited[w]==0) //若顶点w未访问,递归访问它 Cycle(G,w,v,d,has); //从顶点w出发搜索 elseif (w==v && d>1) //u到v存在一条边且回路长度大于1 { has=true; return; } p=p->nextarc; //找下一个邻接点 } } boolhasCycle(AdjGraph *G,int v) //判断连通图G中是否有经过顶点v的回路 { boolhas=false; Cycle(G,v,v,-1,has); //从顶点v出发搜索 returnhas; }[/u][/u]
举一反三
内容
- 0
假设无向图采用邻接表存储,编写一个算法求连通分量的个数并输出各连通分量的顶点集。
- 1
假设一个有向图G采用邻接表存储，分别设计实现以下要求的算法:判断图G中是否存在边<i, j>.[br][/br]
- 2
设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。
- 3
假设图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]采用邻接表存储,设计一个算法求无向图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的连通分量个数。
- 4
无向图采用邻接表存储结构，编写算法输出图中各连通分量的顶点序列。