首页 > 2011年陕西省基础数据要领

2011年陕西省基础数据要领

发布时间：来源：文档文库

小中大

字号：

手机查看

1、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）
有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。
voidPrint(intv,intstart//输出从顶点start开始的回路。{for(i=1;i<=n;i++
if(g[v][i]!=0&&visited[i]==1//若存在边（v,i），且顶点i的状态为1。{printf(“%d”,v;
if(i==startprintf(“\n”;elsePrint(i,start;break;}//if}//Printvoiddfs(intv{visited[v]=1;for(j=1;j<=n;j++
if(g[v][j]!=0//存在边(v,j
if(visited[j]!=1{if(!visited[j]dfs(j;}//ifelse{cycle=1;Print(j,j;}visited[v]=2;}//dfs
voidfind_cycle(//判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。{for(i=1;i<=n;i++visited[i]=0;
for(i=1;i<=n;i++if(!visited[i]dfs(i;}//find_cycle2、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）
有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。
voidPrint(intv,intstart//输出从顶点start开始的回路。{for(i=1;i<=n;i++
if(g[v][i]!=0&&visited[i]==1//若存在边（v,i），且顶点i的状态为1。{printf(“%d”,v;
if(i==startprintf(“\n”;elsePrint(i,start;break;}//if}//Printvoiddfs(intv{visited[v]=1;for(j=1;j<=n;j++

if(g[v][j]!=0//存在边(v,j
if(visited[j]!=1{if(!visited[j]dfs(j;}//ifelse{cycle=1;Print(j,j;}visited[v]=2;}//dfs
voidfind_cycle(//判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。{for(i=1;i<=n;i++visited[i]=0;
for(i=1;i<=n;i++if(!visited[i]dfs(i;}//find_cycle

本文来源：https://www.2haoxitong.net/k/doc/70b21bbf1711cc7930b7166f.html