Kosaraju算法为什么是用图G的反向图的逆后序,而不能是图G的后序?

vivarock

2018-05-24 12:58:52

Personal

Kosaraju算法的关键个人认为还是对强连通性的双向可达性的证明,比如dfs(s)调用过程中访问到了v顶点,这样深度优先搜索隐式的提供了s->v的可达性,而只有逆后序(拓扑排序)才能提供 v->s的可达性,而后序是无法保证这种单向可达性的,可以多测下后序的例子观察这一点,所以从可达性的角度来看,只有逆后序才能提供这点。而原图的逆后序显然不能用于第2次遍历原图,所以只有反向图的逆后序才是正解。从网上又找到个资料,可以从另一个角度来回答这个问题,因为算法的最终目的是找出所有的独立环,那么最后的结果肯定是一个个独立的环,如果把所有的环收缩成一个顶点,那么该图会成为一个有向无环图,所以用整体的看法来看这个问题,我们就应该用拓扑排序来处理图。而通过反向图我们可以先拿到原图中后面的独立环,因为后面的独立环对于前面的独立环是不可达的(拓扑排序性质保证),这样就可以通过遍历拓扑排序拿到独立的强连通环了。PS: 感觉对这个问题的理解,关键还是在于对《算法》中用深度优先搜索处理有向图时,深度优先搜索的逆后序就是拓扑排序的证明需要仔细理解。