请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

老师,如何找出一个无向图中所有的环路径呢?

正在回答 回答被采纳积分+3

1回答

liuyubobobo 2021-03-31 05:44:17

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


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


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


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


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


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


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

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


继续加油!:)

2 回复 有任何疑惑可以回复我~
问题已解决,确定采纳
还有疑问,暂不采纳
微信客服

购课补贴
联系客服咨询优惠详情

帮助反馈 APP下载

慕课网APP
您的移动学习伙伴

公众号

扫描二维码
关注慕课网微信公众号