bfs进行有向图环检测

来源：13-3 有向图环检测和 DAG

慕运维9331189

2020-11-20

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

写回答

1回答

liuyubobobo

2020-11-21

已采纳

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

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

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

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

继续加油！：）

慕运维9331189

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

2020-11-21

共1条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1