找到有向图的环

Question

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

Answer 1

liuyubobobo 2020-05-24 03:18:30

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

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

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

继续加油！：）

• 提问者 慕无忌5505138 #1

  好的，感谢老师！