拓扑排序第一种实现

Question

波波老师，有向图中所有的顶点没一个入度为0的，是不是也可以判断有环无环？

Answer 1

liuyubobobo 2021-09-05 14:13:26

可以的呀。

在这种情况下：https://git.imooc.com/coding-370/Play-with-Graph-Theory-Algorithm/src/master/13-Directed-Graph/07-Topological-Sort/src/TopoSort.java

25 行代码不会执行，因为没有一个节点入度为 0。

28 的 while 也就进不去，因为 q 是空。那么 res 也是空。

38 行就会成立，因为一个图肯定有顶点，但 res 为0，G.V() 一定不等于 res

于是 hasCycle 设为 true。

我们现在的代码依然成立。

继续加油！：）

• 提问者 GameCater #1

  非常感谢！