当前位置：首页 → 问答吧 → 有向图是否存在环的方法以？

有向图是否存在环的方法以？

时间：2011-09-14

来源：互联网

听别人说，用深度遍历可以判断有向图是否有环，请问怎么操作，如有，a->b->c,a->c,和a->b->c,c->a,用深度遍历怎么可以分别啊？请帮忙，谢了。

作者: goodluckhyp 发布时间: 2011-09-14

设置一个pre参数，记录上次访问的节点
访问下一个节点时（不能等于pre），如果某个点已经访问过，那么形成了环。

作者: power721 发布时间: 2011-09-14

如有，a->b->c,a->c,和a->b->c,c->a,用深度遍历都会访问啊，但a->b->c,a->c是无环，而a->b->c,c->a却是有环，那怎么办啊

作者: goodluckhyp 发布时间: 2011-09-14

记录一个bool型的visit数组，如果访问过i结点，则C/C++ code

visit[i]=true;

（visit数组开始全部置为false)
然后dfs时如果访问已经标记的点，说明存在环
如果全部都标记后还没遇到已经标记的点，则没有

判断是否有环，也可以用并查集（我觉得实现很简单）

作者: nuptxxp 发布时间: 2011-09-14

还有，lz没有结贴的习惯吗？

作者: nuptxxp 发布时间: 2011-09-14

令有向图的顶点是 1,2,...,n;用邻接矩阵 A[1..n][1..n]表示有向图:
A[i][j]=1 表示顶点 i 到 j 有边;
A[i][j]=0 表示顶点 i 到 j 无边;
算法如下:
for (;;)
{
检查 A[1][1],A[2][2],...,A[n][n] 是否有 1,若有,返回 "有回路";若没有,继续;
Flag=0;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (A[i][j]!=0) // 若 i 到 j 有一条边
for (k=1;k<=n;k++)
if (A[j][k]!=0) // 若 j 到 k 也有边
{
if (A[i][k]==0) Flag=1; // 发现新路
A[i][k]=1;
}
if (Flag==0) break; // 没有发现新路
}
返回 "没有回路"

作者: icessl 发布时间: 2011-09-14

若用深度搜索,可以这样做:

// 返回 1 有回路
// 返回 0 没有回路
int HasCircle(int SrcDot,int Path[],int Deep)
{
int i;

for (i=1;i<=n;i++)
if (A[SrcDot][[i]!=0) // 若 SrcDot 到 i 有边
{
if (i==SrcDot || 在 Path[0],Path[1],...,Path[Deep-1] 中有一个等于 i) return 1;
Path[Deep]=SrcDot;
if (HasCircle(i,Path,Deep+1)!=0) return 1;
}

return 0; // 没有回路
}

主调函数是:
int Path[N];

for (i=1;i<=n;i++)
{
if (HasCircle(i,Path,0)!=0) return 1; // 有回路
}
return 0;

作者: icessl 发布时间: 2011-09-14

topological sorting is ok for DG

作者: fairywell 发布时间: 2011-09-14

有向图是否存在环的方法以？

热门阅读

热门下载