各位牛人，在无向图里面怎么把环都找出来啊？？有什么好办法吗？？

rt,我现在想的办法就是任选一个顶点开始找一棵树，
发现有新的节点回到前面，就认为找到一个环。
这个办法，我自己不知道对不对，也不知道效率如何，有什么更好的办法吗？？
那些数据结构的书里面都没有讲到这个，那位牛人指点一下。
告诉我应该看什么书也很有帮助啊。
谢谢。

7 个解决方案

#1

我认为就只有搜索。

#2

从任意一个点开始，递归搜索，搜过的点标记一下。

如果还有没有标记过的点，再从这个点递归搜索。

应该不复杂。

#3

我一开始想到的是构造一个生成树.
然后往生成树上添一条边,就得一个环..
但好像得不到全部的环的...
还在想办法...

#4

一次深度优先遍历不就可以了么，发现了反向边就发现了环

#5

to starfish
一次不行吧？如果这个图是不连通的……

#6

真的吗？？那我先编一段试试看了。
打算先把不连通的几个部分都找出来，再把只有一个连接的端点去掉，然后开始搜，有什么问题吗？？

#7

不用先把不连通的找出来。

按照我的方法，没错的：）