【算法请教】怎样在O(V)的时间内判断一个无向图是否有环?

YHZhu 发布于 2010/07/12 08:10
阅读 987
收藏 0

最近在看图论,有个问题想不明白,拿出来请教一下。

给定一个无向图G=(V, E), 怎样在O(V)的时间内判断这个图是否有环?

加载中
0
z
zihong_chen

感觉可以深搜

先建立一个顶点颜色表C[v] 
   0 白色,未被访问过的节点标白色
   -1 灰色,已经被访问过一次的节点标灰色
   1 黑色,当该节点的所有后代都被访问过标黑色 

仍然是按图的节点深度遍历,访问到k时,V若被访问过,那么有2种状态:
C[k]=-1,存在环
C[k]=1,不是环

时间复杂度O(n+e)

0
YHZhu
YHZhu

是啊,DFS的时间复杂度是O(V+E),但是有没有问题要求用O(V)的时间啊!

返回顶部
顶部