Question

c语言，无向图如何检测是否有环？

求代码

Answer 1

遍历一遍，判断图分为几部分（假定为P部分，即图有 P 个连通分量）
对于每一个连通分量，如果无环则只能是树，即：边数＝结点数－1
只要有一个满足 边数 > 结点数－1
原图就有环
将P个连通分量的不等式相加，就得到：
P1:E1=M1-1
P2:E2=M2-1
...
PN:EN>MN-1
所有边数(E) > 所有结点数(M) - 连通分量个数(P)
即： E + P > M 所以只要判断结果 E + P > M 就表示原图有环，否则无环.

实例代码如下：

http://www.cnblogs.com/xwdreamer/archive/2011/06/11/2297008.html