怎样理解Kosaraju算法( 三 )
5 这时根节点团的出边就变成了入边。所以根节点团不能到达其他的强连通分量团。
6 所以这时候从根节点dfs就只能访问到根节点团（根节点所在的强连通分量）的内部的节点，其他的团同理。
■网友
推荐阅读的中3.4节, 思路很清晰, 解释得非常直观. 我大概写一下我的阅后总结:
首先, 你得熟悉有向图(digraph)的深度优先搜索(DFS), 前序(preorder), 后序(postorder), 逆后序(reverse postorder), 有向图的逆(transpose graph);如果把一个强连通分量中的所有点浓缩(contract)成一个点, 那么原图G就变成了一个有向无环图(DAG);易证, 一个DAG至少有一个源(source)和一个汇(sink);如果我们从sink分量中的任一节点开始DFS, 那么我们就不能到达其他任何连通分量, 而只能遍历这个sink分量中的所有节点;我们要是能够很容易地就找到sink分量中的一个节点就好了, 可貌似并不是很容易;但我们可以很容易找到source分量中的一个点: 后序列表中的最后一个点(i.e. 逆后序列表中的第一个点). 注意, 后序列表中的第一个点并不一定在sink分量中;不过没有关系, G的逆(i.e. G\u0026#39;)的source不就是G的sink么? 搞定!
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 怎样成为一名合格的Python程序员?
- 怎样评价华为、诺基亚、中兴中标中国移动高端路由交换设备扩容集采
- 怎样评价类似前橙会、百老汇、南极圈这样类型的离职帮抱团，对企业的积极意义和消极意义