bfs进行有向图环检测

Question

bobo老师，你在课上讲了dfs和bfs进行无向图环检测；dfs进行有向图环检测，没有讲bfs进行有向图环检测。
我想了想不太会，网上没有搜到好的答案（有些甚至说bfs不可以进行有向图环检测），要不你在有向图章节加一个文字版补充吧，万分感激：）

Answer 1

liuyubobobo 2020-11-21 14:53:40

我不确定你是否学习了拓扑排序。使用 bfs 的思路判断有向图中的环，本质就是拓扑排序。

在这一章的后续，我会介绍拓扑排序，你会看到，

1）拓扑排序的过程就是 bfs：从入度为 0 的节点出发，向外层层拓展，找到新的入度为0的节点；

2）如果通过拓扑排序，不能遍历有向图中的所有节点，说明图中存在环。

继续加油！：）

• 提问者 慕运维9331189 #1

  想了想，确实拓扑排序就是bfs的思路，谢谢bobo老师：）