检测图中是否有cycle

with_god 发表于 2015-12-13 12:14
http://www.cnblogs.com/tenosdoit/p/3644225.html 这个blog里解释的比较详细。

非常感谢

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 14:37
你数一下所有点的入度，然后把这些存放在一个HashMap里面。然后，标准算法里面删Edge，你就删入度。然后 ...

我给你发私信了

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

循环的退出条件就是不存在入度为0的点。如果还有入度为0的点，那么就删去这些点；如果没有入度为0的点，则退出循环，此时如果还有未处理的点，说明图中有环，否则图中无环。

stellari 发表于 2015-12-14 20:27
循环的退出条件就是不存在入度为0的点。如果还有入度为0的点，那么就删去这些点；如果没有入度为0的点， ...

恩恩·对的···你说的是对的嘿嘿
·可以按照拓扑排序的步骤来做，最后将拓扑排序的结果集合元素与原来graph中node数来对比