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

admin2017-11-14  41

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

选项

答案用邻接矩阵存储时,可用以下方法实现: void Print(int v,int start){//输出从顶点start开始的回路 for(i:1;i<=n:i++) if(g[v][i]!=0&&visited[i]==1){ //若存在边(v,i),且顶点i的状态为1 printf(”%d.t,V); if(i==start)printf(”\n”): else Print(i,start): break; }//if }//Print void dfs(int v){ visited[v]=i; for(j=1;j<=n;j++) if(g[v][j]!=0) //存在边(v,j) if(visited[j]!=1){if(!visited[j])dfs(j);}//if else{cycle=1;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): }

解析
转载请注明原文地址:https://jikaoti.com/ti/AifjFFFM
0

最新回复(0)