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

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

admin2018-08-12  68
问题 假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注意：图中不存在顶点到自己的弧)
选项
答案用邻接矩阵存储时，可用以下方法实现： 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”，v)； if(i==start)printf(“＼n”)； else Print(i，start)； break； }／／if }／／Print void dfs(int v){ visited[v]=l； 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)； } 提示：此题考查的知识点是图的遍历。有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问，已访问但其邻接点未访问完，已访问且其邻接点已访问完。下面用0、1、2表示这三种状态。前面已提到，若dfs(v)结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若找出u的下一邻接点的状态为1，就可以输出回路了。
解析
转载请注明原文地址:https://kaotiyun.com/show/nMRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)