1回答

liuyubobobo

2021-03-31

我们写的判断是否有环的算法，找到一个环就终止了。

要想找到所有环，只能在 dfs 的过程中，找到一个环，标记上（可以给当前找到的环设计一个哈希函数，用哈希表标记），然后继续回溯查找。

这个算法是指数级别的。因为一个无向图中的环的数量，就可能是指数级别的。

在这个问答里，我构造了一个例子，来揭示为什么从一点到另一点的路径个数是指数级的：http://coding.imooc.com/learn/questiondetail/140717.html

看看是否有启发？看看你能不能构造出，为什么对于一个无向图中的所有环，其个数是指数级别的？

因为这个算法是指数级别的，一方面，在面试中（或者竞赛中），很少会出现找所有环的问题；另一方面，如果出现了，一定点的数量非常小（比如 20）。这样的话，可以利用状态压缩做优化（可以参考这个课程介绍哈密尔顿回路的解法。但他仍然是指数级别算法。）

除非，你面对的图是一种有某种特殊性质的图，比如有其他约束条件，使得图中的环的个数不可能是指数级别。对于这种情况，只能具体问题具体分析了。

（最简单的例子，如果高速你一个联通图有 n 个顶点和 n 条边，这个图中最多只可能有 1 个环）

继续加油！：）

2

0