怎样理解Kosaraju算法( 二 )
1. dfs(s)start-\u0026gt;dfs(v)start-\u0026gt;dfs(v)end-\u0026gt;dfs(s)end（s，v属于同一连通分量且GR图中有s-\u0026gt;v） 2. dfs(v)start-\u0026gt;dfs(v)end-\u0026gt;dfs(s)start-\u0026gt;dfs(s)end （s，v属于两个连通分量）
接着，在G图中按照“···，s,···，v，···”的逆后序进行深度优先搜索，若存在s-\u0026gt;v，则说明s，v在GR图中存在v-\u0026gt;s的路径，则反过来说明GR图中的情况二是不可能出现的。所以“···，s,···，v，···”的逆后序从侧面说明了GR图中s-\u0026gt;v。
总结：在G图和GR图中都存在s-\u0026gt;v，则说明s-\u0026gt;v强连通。
补充，在图G中使用GR的逆后序，我个人认为就是一种信息的传递，即告诉G图，GR图中s已经是在v前面的了（s-\u0026gt;v），你只要能按照这个顺序再来一遍深度优先搜索并且搜索出s-\u0026gt;v，就可以直接得到s和v强连通的结果。
■网友
自己提的问题自己回答一下。
Kosaraju算法的步骤如下：
1.对有向图G采用深度优先遍历得到访问时间的排序。假设我们采用dfs(s)对顶点做深度优先搜索，那么访问时间就是dfs(s)的leaving time，leaving time的从大到小排序就是G的一个伪拓扑排序。具体一点的过程是这样的：dfs(s) startdfs(v)startpush(v)dfs(v)endpush(s)dfs(s)end这种在递归调用之后将顶点入队列的方式叫逆后续排序(reverse post)，在无环图中这种排序方式就是拓扑排序。
2.从leavingtime最长也就是位于栈顶的顶点s开始做G的逆向图(GR)深度搜索，得到若干搜索树即为图G的强连通分量。
有没有很神奇，按照G伪拓扑排序对G的逆序图直接深度优先搜索就可以得到强连通分量。我当时看到这里也是懵逼的，凭啥 ？
举个栗子，从GR中做对s做深度优先搜索，我们发现可以访问v，那么必然存在s到v的一条路径。下面关键证明GR中存在v到s的路径，即G中存在s到v的路径。
由于GR中我们是先访问s再访问到v，显然在G中dfs(v)的leavingtime是小于dfs(s)的，因为伪拓扑是通过栈的方式保存访问顶点点，最先结束dfs的顶点排在最后，那么可能存在以下几个访问顺序：1. dfs(s)start-\u0026gt;dfs(v)start-\u0026gt;dfs(v)end-\u0026gt;dfs(s)end2. dfs(v)start-\u0026gt;dfs(v)end-\u0026gt;dfs(s)start-\u0026gt;dfs(s)end如果是可能性2的话GR中对s做深度优先搜索的时候不可能访问到v，因此一定是可能性1。也就是说在G中存在s到v的一条路径。
以上的解释我敲完之后异常蛋疼。下面介绍一种非常容易定性理解的方法：
将所有的强连通分量都看作一个整体，那么这些强连通分量构成一个单向无环的图。我们如何遍历这个图找到所有强连通分量，最合理的方式是逆向遍历，从没有子节点的强连通分量开始，这样你做dfs的时候一定是在同一个连通分量里面做，不会跑到下一个连通分量中。
■网友
这个算法理解花了半天时间，理解了以后发现简单的很，自己写的一篇博客，分享给想快速搞懂的小伙伴们~
为什么Kosaraju算法是正确的？--带你完全搞懂有向图的Kosaraju算法 - CSDN博客
【怎样理解Kosaraju算法】
■网友
说一种理解思路，我觉得挺好理解的。
1 先把所有的强连通分量缩成一团（最近知道了这个叫做缩点）
2 团与团之间的出入边不变，所以整个图就变成了一个团的有向无环图
3 对这个有向无环图进行dfs会有一个dfs树，第一次dfs处于根节点的团一定是最后完成的，这个时候根节点全是出边（不然怎么叫根节点）
4 所以在第二次逆向dfs中，根节点团就是最先访问的。
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 怎样成为一名合格的Python程序员?
- 怎样评价华为、诺基亚、中兴中标中国移动高端路由交换设备扩容集采
- 怎样评价类似前橙会、百老汇、南极圈这样类型的离职帮抱团，对企业的积极意义和消极意义