找到有向图的环

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

慕无忌5505138

2020-05-23

老师您好，似乎课程里只讲述了如何判断有向图有环，而没有讲述如何找到有向图里的环？关于这个问题我搜索了一下，感觉有效内容比较少，老师您有什么推荐的资料吗？或者课程里有但是我没注意到？

写回答

1回答

liuyubobobo

2020-05-24

已采纳

在检测环的过程中，用一个 pre 记录每一个节点是从哪个节点来的，当找到环的时候，通过 pre 逆推就能得到具体的一个环。

这个方法在课程中使用过很多次？试试看？

但是，如何找到有向图中的所有环，是指数级的，这是因为一个图中的环的总数可能是指数级的。可以参考这个问答，意思是类似的：http://coding.imooc.com/learn/questiondetail/140717.html

继续加油！：）

慕无忌5505138

好的，感谢老师！

2020-05-27

共1条回复

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

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

1591 学习 · 324 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1