检测图中是否有cycle

检测graph中是否有cycle，有没有同学指导一下思路和方法？
图分为有向图和无向图两种情况然后图中边的情况可以是由邻接矩阵给出的

yucheyang2 发表于 2015-12-13 10:37
有向图的话直接上拓扑排序，拓扑排序的最后做完时候就能判断是不是有环了。

刚刚研究了一下拓扑排序，貌似如果是有向图有环的话，每一个点都是有入度的吧？然而拓扑排序我先要找一个入度为0的点，这样子怎么进行拓扑排序呢

补充一下···就是我还是按照DAG来做，只不过是当我发现某一个点的入度是负数，则代表有cycle，不知道理解的对不对

JamesJi 发表于 2015-12-14 03:03
刚刚研究了一下拓扑排序，貌似如果是有向图有环的话，每一个点都是有入度的吧？然而拓扑排序我先要找一个 ...

你数一下所有点的入度，然后把这些存放在一个HashMap<Node_Identifier, Integer>里面。然后，标准算法里面删Edge，你就删入度。然后做完之后，如果HashMap还剩下什么，就是有环，否则输出拓扑排序的顺序。

yucheyang2 发表于 2015-12-13 10:37
有向图的话直接上拓扑排序，拓扑排序的最后做完时候就能判断是不是有环了。

能不能给一个具体的例子？
还有就是如果无向图的时候应该怎么做呢？我现在想到的是用一个标记数组，如果发现这个点已经被标记过，那么说明有环的存在，然后方法应该是这样，可是我怎么来表示一个点的相邻的点或者说怎么表示边呢？

用Set记录访问过的节点，DFS或者BFS走一遍


并查集

无向图经典做法是两个index一个一次走一步一个一次走两步如果相遇就有cycle

挖土机 发表于 2015-12-12 23:28
无向图经典做法是两个index一个一次走一步一个一次走两步如果相遇就有cycle

我好像记得lc里面有一个类似的

有向图的话直接上拓扑排序，拓扑排序的最后做完时候就能判断是不是有环了。

lcl3356897 发表于 2015-12-12 22:45
用Set记录访问过的节点，DFS或者BFS走一遍

这个是无向图的情况吧？

lcl3356897 发表于 2015-12-12 22:45
用Set记录访问过的节点，DFS或者BFS走一遍

你好，我写了一个··不知道对不对··
https://gist.github.com/JamesJi9277/874eb933028d3a557f9b

无向图中假设n个点 超过n-1条边就一定有环

http://www.cnblogs.com/tenosdoit/p/3644225.html 这个blog里解释的比较详细。