【引用】willshy
发表于:2007-10-24 15:29:189楼 得分:1
无向图的深度遍历中,访问到已访问过的节点,可以得出 “存在环” 的结论;但在有向图中并不是这样。
我把我的算法详细说下,先建立一个顶点颜色表C[N]
0 白色,未被访问过的节点标白色
-1 灰色,已经被访问过一次的节点标灰色
1 黑色,当该节点的所有后代都被访问过标黑色
仍然是按图的节点深度遍历,访问到V时,V若被访问过,那么有2种状态:
C[V]=-1,程序跳出,存在环
C[V]=1,程序继续,这不是环
时间复杂度O(n+e)
参考了一下 willshy 回帖,直接试着写了一段代码实现,不知道是否考虑周全,请批评指正。
template<class NameType,class DistType>
int Graph<NameType,DistType> ::DFS(int v,int visited[])
{
//cout<<GetValue(v)<<' '; // GetValue() please add
visited[v]=-1;
int w=GetFirstNeighbor(v);
while(w!=-1)
{
if(visited[w]==0)
{
DFS(w,visited);
visited[w]=1;
}
else if (visited[w]==-1) {
cout<<"graph must be acyclic";
return 0;
}
w = GetNextNeighbor(v,w);
}
return 1;
}
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/guyuan1983/archive/2008/03/18/2195084.aspx