假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)

admin2019-08-15  25

问题 假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)

选项

答案 用邻接矩阵存储时,可用以下方法实现: void Print(int v,int start){ //输出从顶点start开始的回路 for(i=1;i<=13;i++) if(g[v][i]!:0&&visited[i]==1){ //若存在边(v,i),且顶点i的状态为l printf("%d",v); if(i==start)printf(”\n”); else Print(i,start); break; }//if }//Print void dfs(int v){ visited[v]=1 ; for(j=l;j<=n;j++) if(g[V][j]!=0) //存在边(v,j) if(visited[J]!=1){if(!visited[j])dfs(j);}//if else{cycle=l;Print(j,j);} visited[v]=2; } void find—cycle(){ //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量 for(i=1;i<=n;i++)visited[i]=0; for(i=1;i<=n;i++)if(!visited[i])dfs(i); } 提示:此题考查的知识点是图的遍历。有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问,已访问但其邻接点未访问完,已访问且其邻接点已访问完。下面用0、1、2表示这三种状态。前面已提到,若dfs(v)结束前出现顶点M到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若找出u的下一邻接点的状态为1,就可以输出回路了。

解析
转载请注明原文地址:https://kaotiyun.com/show/SdCi777K
0

最新回复(0)