强连通分量算法设计思路分析
本文从多个角度去讨论了强连通分量算法的设计思路，并重点分析了算法中的图转置操作的意义。
本文的内容是基于算法导论22.5节的深度分析，编写日期2019/1/22,20日掌握算法导论day13
【为什么要转置图G？】
为什么不直接按照正时间次序对原图G进行二次深度优先搜索，这样我觉得也行啊，分析见下例题
Exercises 22.5-3
Professor Bacon claims that the algorithm for strongly connected components
would be simpler if it used the original (instead of the transpose) graph in the
second depth-first search and scanned the vertices in order of increasing finishing
times. Does this simpler algorithm always produce correct results?
设想对上图应用指定的升序式算法, 图中有A, B, C 三个顶点, A->B, B->A, B->C 三条边.
如果首次 DFS 从 B 开始, 先向 A 遍历, 则访问顶点顺序为 (B (A, A) (C, C) B)
升序排列 finishing time 是 A, C, B. 这样第二次进行 DFS 则应从 A 开始, 该算法
结果显示 A, B, C 是一个强连通组件, 而实际情况不是如此.
该算法不能保证通用性, 只有在选择特殊顶点作为起始点, 以及规定邻接表顺序的情况下,
结果才有可能是正确的.
转置的目的：
- 让每颗遍历树都不存在外国人（连通分支之外的点）
- 对图进行转置后，导致每次探索流程都必然会被阻隔在单个强连通分支之内，这就是转置的意义
- 通过22.5-3习题的分析知道，如果不转置，即使按照特定的时间戳去遍历图，也会在不经意间将两颗连通分支的树合并到一颗
下面开始分析强连通算法的设计思路
- 【算法设计思路分析】
- 设计强连通分量算法的难点分析：有向图强连通与弱连通交错结构，导致了生成的遍历树有可能混杂了多个连通分支。于是我们希望将强连通和弱连通交错的因子降低，而图转置恰巧能做到这点（图转置能够起到关闭弱连通路径的功能）
- 我们希望通过特定的手法、顺序去搜索图以使得产生的遍历树都是独立的连通分支，因此我们需要去探究深度优先算法的遍历树的子树之间的关系。
- 转置后（也就是把去国外的桥砍掉后），紧接着，我们发现如果设置起点从连通分支内进行遍历，那么必然产生一颗独立的DFS树，这颗树是一家人，都是一个连通分支内的。我们还发现连通分支树之间的顺序是按照固定的规则来排列的，他们都有满足特定规律的时间戳（定理22.14）。
- 【强连通问题与其他深度优先算法问题对比】
- 强连通分量问题使用了两次深度优先算法，这里使用的深度优先算法是普通的深度优先图遍历算法。
- 在其他深度优先算法的应用场景，我们经常是修改深度优先算法终止的条件来解决问题；不同的是，而在强连通问题中，我们通过修改输入空间的图结构来利用深度优先这个工具以求得连通分支，我们并没有在这里修改深度优先算法的终止条件。
- 【分析分量图的意义】
- 我们可以将分量图看做是一种分析工具，他就是一种简化图，他将包含多个连通分支的有向图收缩抽象，从而将图大大简化。
- 【定理之间的关联】
- 引理22.13是强连通分量算法的关键性质，正是因为它才保证了算法的正确性。换句话说，本节算法正是利用了 分量图的有向无环性 而设计的
- 分量图的有向无环性 给22.3节深度优先算法的众多括号化结构相关定理创造了使用条件，因此我们便能导出许多基于时间戳的结论。于是，我们便能通过算法控制和利用时间戳（这等价于我们能够决定我们产生遍历树的顺序，进而可以将连通分支的遍历树互相分割开来）
下文给出CLRS中相关定理原文