admin管理员组文章数量:1566645
2024年7月25日发(作者:)
1、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有
向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点
到自己的弧)
有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但
其邻接点未访问完;已访问且其邻接点已访问完。下面用0,1,2表示这三种状态。前面已提
到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。对应程
序中v的状态为1,而u是正访问的顶点,若我们找出u的下一邻接点的状态为1,就可以输
出回路了。
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
void dfs(int v)
{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); }//if
else {cycle=1; Print(j,j);}
visited[v]=2;
}//dfs
void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量。
{for (i=1;i<=n;i++) visited[i]=0;
for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);
}//find_cycle
2、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有
向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点
到自己的弧)
有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但
其邻接点未访问完;已访问且其邻接点已访问完。下面用0,1,2表示这三种状态。前面已提
到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。对应程
序中v的状态为1,而u是正访问的顶点,若我们找出u的下一邻接点的状态为1,就可以输
出回路了。
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
void dfs(int v)
{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); }//if
else {cycle=1; Print(j,j);}
visited[v]=2;
}//dfs
void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量。
{for (i=1;i<=n;i++) visited[i]=0;
for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);
}//find_cycle
3、在有向图G中,如果r到G中的每个结点都有路径可达,则称结点r为G的根结点。编写
一个算法完成下列功能:
(1).建立有向图G的邻接表存储结构;
(2).判断有向图G是否有根,若有,则打印出所有根结点的值。
版权声明:本文标题:2015年全国JAVA最新版本高级 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1721914679a904805.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论