怎样理解Kosaraju算法
以《算法》第四版中的实现为例，它旨在让每次递归探索中的所有顶点属于同一强连通分量。所以可以这么理解，当递归进入一个强连通分量中时，把它锁死在这个强连通分量中。
**核心在于封死连通分量往外走的路**
而如何封死呢？该算法采用的是深度优先搜索，如果遇到了已经访问过的顶点则不再访问，那么如果能让一个分量内往外走的顶点已经被访问过了，是不是就能够锁死了呢？所以下图中，为了让5中的顶点正确关联上强连通分量编号，我们需要事先锁死H和C这两个顶点。
上图为一个有向图，每个绿色方框为一个强连通分量，我们想要做的就是为这几个绿色方框内的顶点关联上对应的分量编号(绿框的编号)。
我们将以深度优先搜索去穿越这幅图，但是我们希望每次探索都控制在一个绿色方框内，如1，进去了肯定到不了其他分量，而5通过顶点E和C、通过G和H连接起来了，它能够到达其他分量，所以我们希望当在分量5中探索时，如果到了E点，希望能够得到一个信息:不应该继续探索C顶点(H点同理)。
如何做到呢？考虑到深度优先搜索的特性：如果一个顶点已经探索过了，将不会再探索。那么我们只要保证在分量5内的顶点被探索时，C顶点与H顶点已经被探索过就能实现我们的目标。分量2、3、4之间的先后顺序同理。一般情况下我们使用DFS时都是从索引为0的顶点开始探索(或者其他的顶点，可视为从随机顶点开始)，无法保证分量1(还有分量3)在分量5之前探索完毕。在这个图中，无论是采用前序、后序还是逆后序，都无法达到我们的要求。
根据逆后序的性质，我们知道先探索完的顶点将会被放在栈的底部，其顺序是比较靠后的，所以我们可以利用这一点让分量5中的顶点顺序靠后，如何做到呢？ 我们观察一下图并联想一下食物链，发现分量5实际上是处于食物链较的顶端的位置，因为他通过E和G侵入了其他群落，不考虑群落内的关系，为了颠覆分量5的统治地位，我们需要反转各群落之间的关系——反转图。 
**一个图的反向图有着和其相同的强连通分量划分情况**这样一来，之前被分量5掠夺的群落反过来掠夺它了，也就是说，之前在分量5中探索时能够走出去的路全都反转了，走不出去了，这就给我们机会确定了分量的范围。如果你是从5开始，那么它走不出去，它内部的顶点先探索完毕，放入栈的底部；如果你是从3或者1开始，那么又将会走进5，所以5中的所有顶点也会放入栈的底部。所以反向图中，无论是从从哪里开始，都能保证在逆后序中，分量1和分量3中能够至少有一个顶点在栈中的位置处于所有5中的顶点之上。上面这幅图的逆后序(之一)为(假设从C开始)：\u0026gt; D A B F G E C I H J 我们用这个逆后序去深度优先搜索(正向)图，可以发现每次递归都是在同一个强连通分量之中。当然大家可以多试试反向图中的不同的逆后序，得到的结果是一样的。举一反三，虽然这个图中的分量比较少，但基于逆后序的性质，可以推广到所有的有向图中。
这就是我理解的为什么要用反向图的逆后序去DFS正向图。
■网友
核心的思想或许可以总结成两点：
圈反过来也是圈把圈反一半过来会得到两条路径你可以认为第一次搜索之后按倒过来的顺序重新搜，就是为了避开上次走过的路径。如果这次能找到另一条路径，和上次那条拼起来就是个圈了。
■网友
为了证明s和v强连通，
首先，运用GR图得到一个逆后序，该逆后序可以写成如下形式：
···，s,···，v，···
从该形式我们可以推断出两种情况：
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 怎样成为一名合格的Python程序员?
- 怎样评价华为、诺基亚、中兴中标中国移动高端路由交换设备扩容集采
- 怎样评价类似前橙会、百老汇、南极圈这样类型的离职帮抱团，对企业的积极意义和消极意义