DFS搜索树上有返祖边,等价于图中至少存在一个环。
充分性显然,必要性。
如果是无向图,那就只有树边和返祖边,不存在横插边,没有返祖边那就是一棵树,与图中有环矛盾。
有向图多了横叉边,但是这样不是环,是个DAG,也矛盾。
这个结论常用于深搜判环。
在Fish Graph一题中,dfs
只能找到一个任意环,但是因为我们有保证环上至少有一个度数不小于4的点(起点),所以这个环要么满足题意,要么一定可以调整得到一个新的符合题意的环,而且这个新环必然在回溯的过程中被更新到,所以这样dfs
是正确的。
这个做法毫无一般性。
AlexWEI的BFS的做法值得研究一下。
下面证明,BFS中找出的环,一定是极小环。
注意,只是极小的环,不是最小的环,BFS也只能找出任意环,但是可以保证任意环是一个极小的环。
假设它不是极小的环。
那么环内就还有一条边,而且由于BFS树中的非树边只能在同一层或者相邻两层,所以里面的更小的环必然更早被搜到,那么这个任意环就不是被搜到的环了。
BFS树上没有返祖边,只有横插边,而且层数不能相差超过1,如果没有走到横插边,那么就是树,就没有环了,矛盾。(所以也是等价于至少存在一个环,而且一定走到的是极小环)。
标签:题意,返祖,插边,极小,证明,BFS,关于,一些,任意 From: https://www.cnblogs.com/zhangchenxin/p/17814344.html