求解强连通分量算法之---Kosaraju算法

本文介绍了强连通分量（Strongly Connected Component, SCC）的概念及其在有向图中的应用，并详细阐述了Kosaraju算法的工作原理及其实现过程：
问题描述
强连通分量是指在一个有向图中，任意两个顶点之间都可以互相到达的最大子集。无向图中则称为连通分量（Connected Component），可通过并查集或DFS求解。
缩点概念
在实际应用中，通过将每个强连通分量视为一个独立节点进行处理（缩点），可以显著降低图的复杂度。这种简化后的图必然是DAG（有向无环图）。
Kosaraju算法
算法分为三步：

• 对原图进行DFS遍历并记录完成顶点顺序至栈S。
• 将原图转置为逆向图GR。
• 按照栈S中的顶点顺序对GR进行DFS遍历，在每次遍历形成的一颗搜索树即代表一个强连通分量。
  Java实现
  提供了一个基于Java的KosarajuSCC类，默认使用逆后序遍历生成伪拓扑排序序列作为输入参数调用构造函数，并支持自定义输入序列参数。
  时间复杂度分析
  算法的时间复杂度为O(V+E)，其中V为顶点数，E为边数。该结论基于两次DFS遍历及一次逆向边构建过程得出。

本文提纲：

• 问题描述
• Kosaraju****算法

问题描述：

强连通分量是什么（Strongly Connected Component）（也被称为强连通子图, Strongly Connected Subgraph）？

为了更好地理解这一概念，在有向图中存在强连通分量是可能的，在无向图中则不可能存在这样的结构。此外，在这种情况下（即讨论的是无向图），我们通常将其对应的子图为称其为其对应的"弱"强连通分量或简称为其对应的"普通"强连通分量。在实际应用中，在确定如何求解这些特定的子集时（即计算这些子集的具体数量或特征），可以选择使用并查集算法或者深度优先搜索方法（DFS）。

看一张取自wiki的图就明白什么是强连通分量了：

以上用虚线围绕的部分就是一个强连通分量，因此上图中总共含有三个。

该强连通分量具有这样的性质：即对于任何两个顶点u和v，在该强连通分量中都满足存在从顶点u到顶点v的路径，并且同样地有从顶点v到顶点u的路径。

例如，在图中包含a、b、e这三个顶点的集合所形成的子图中，任何两个顶点之间都可通过路径连接。

顺便也介绍一下有关“缩点”的概念：

考虑到强连通分量的独特性质，在许多实际应用场景中

缩点后得到的结果图必定是一个DAG（有向无环图）。我们可以采用反证法来证明这一结论：假设原图中存在至少一个环路，则根据强连通分量的定义可知，在这种情况下至少有两个顶点之间存在双向可达性关系。然而，在进行了一次缩点操作后，则可以用一个节点来代表这个分量。这与假设矛盾。因此原命题成立。
对于上文中的示例图而言：
经过一次缩点操作后，则可以用一个节点来代表这个分量。

设(a，b，c) -> a'，(f，g) -> b'，(c，d，h) -> c'

因此最后的图就可以表示为：

更加具体，更加严谨的表述，可以参考：

http://en.wikipedia.org/wiki/Strongly_connected_component

Kosaraju****算法

首先摘录一段wiki上的算法过程描述：

Kosaraju's algorithm is a widely recognized algorithm in graph theory. It employs a two-step approach to identify strongly connected components within directed graphs. The first step involves constructing the transpose of the original graph, which means reversing all its edges. In the second step, vertices are processed in the order of finishing times obtained from performing a depth-first search (DFS) on the transposed graph. This method ensures that each strongly connected component is identified correctly and efficiently. The algorithm proceeds as follows: first, it performs a DFS on an arbitrary starting vertex and records each vertex's finishing time when it has no more unexplored edges to traverse. After completing this initial pass, it processes all vertices again in decreasing order of their finishing times by performing another round of DFS on the transposed graph. This process effectively identifies all SCCs (strongly connected components) present in both orientations of the original and transposed graphs.

1. Let G be a directed graph and S be an empty stack.

2. While S does not contain all vertices:
   1. Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.

3. Reverse the directions of all arcs to obtain the transpose graph.

4. While S is not empty:

   1. Extract the top vertex v from stack S.
   2. Conduct a depth-first search starting at vertex v. This will identify all reachable vertices, forming a strongly connected component that includes v. Document this discovery and remove both these vertices from graph G and stack S.
   3. Alternatively, a breadth-first search (BFS) could serve as an alternative to depth-first search.

在步骤2-a中进行观察后发现，在使用基于深度优先搜索（DFS）的方法进行图着色时所执行的操作非常相似。值得注意的是，在这里讨论的图并不一定具有有向无环图（DAG）的性质。而传统的基于DFS的拓扑排序方法仅适用于DAG结构。

在执行深度优先搜索（DFS）操作时，在将各个顶点加入集合的过程中通常会采用以下几种主要的方式：包括按层次依次插入、按照特定排序排列以及基于某种优先级选择等方法。这些策略总共可以分为四种不同的具体实施步骤：

• Pre-Order，在递归调用dfs之前将当前顶点添加到queue中

• Reverse Pre-Order，在递归调用dfs之前将当前顶点添加到stack中

• 后序遍历，在深度优先搜索（DFS）完成之后将当前顶点被插入到队列中

  • 逆后序遍历，在深度优先搜索（DFS）完成之后将当前顶点被压入栈中

该方法的应用范围最为广泛；就目前情况来看，在步骤2-a以及拓扑排序的过程中其核心技术在于使用Reverse Post-Order顺序来遍历顶点集合。

对于有向无环图（DAG），通过Reverse Post-Order策略能够获得一个明确的顶点集合序列（即表示对该图进行完整的topological sort）。然而，在面对非-DAG结构时（如复杂网络中的某些节点间存在循环依赖的情况），采用同样的方法所得出的结果被称为一种"pseudo-topological sort"（伪topological sort）。这之所以被称为"pseudo-topological sort"的原因在于其无法完全满足topological sort所需的基础偏序关系要求。例如，在文中第一幅图中应用这种"pseudo-topological sort"方法所得出的结果可能包括多个不同的可能性（result's non-uniqueness is worth further discussion），具体细节可参考有关topological sort的技术解析部分。

(a，b，e，c，d，h，g，f)

将结果和原图对比，可以发现，结果不满足偏序关系，因为存在回向边：

e->a，d->c，h->d，f->g

这些回向边是构建强连通分量的核心。在Kosaraju算法中作为第三步的操作是将图进行反转。反转操作后，原来的那些关键反向边都被转换成了正向连接。

a->e，c->d，d->h，g->f

将转置后的图遵循上述伪拓扑排序所列顶点出现的顺序(a,e,b,c,d,h,g,f)执行深度优先搜索操作，并将其归类为步骤4

每一次DFS运行都会生成一棵搜索树，在图中对应的就是一个强连通分量。具体来说，在执行过程中，在访问节点a后会依次访问节点e和b等后续节点。随后逐步返回时发现这些被访问过的路径形成了一个完整的回路结构，则可以确定a、b、e构成了一个强连通分量。同样地，在整个遍历过程中不断重复这一逻辑推理过程，则会得出c、d、h各自形成了各自的强连通分量以及g、f也各自形成了各自的强连通分量等结论。

回顾一下Kosaraju的主要步骤：

1. 计算其Reverse Post-Order, 即所谓的伪拓扑排序
2. 通过转置操作获得GR
3. 按照第一步所得顶点序列, 依次进行深度优先搜索以获得若干棵生成树
4. 每一棵生成树对应一个强连通分量

诚实地讲，在研究这个算法时会发现其构思非常巧妙。具体来说，在实现这一功能时采用了独特的思路：首先通过某种方式突出了回向边的作用，在对图进行转置后（即将有向边的方向反转），再按照之前得到的顶点序列依次对其进行深度优先搜索（DFS）。经过测试与验证可知该算法确实能够正常运行，并且在直观上也容易验证其正确性；然而在实际操作中却总感觉有些难以理解：尽管实现起来非常直接明了。

使用Java的实现代码：

 public class KosarajuSCC {

    
  
    
 	private Digraph digraph;
    
  
    
 	private int V;
    
  
    
 	private boolean[] visited;
    
  
    
 	private int[] components;
    
  
    
 	private List<List<Integer>> sccs;
    
  
    
 	// record the current component id
    
 	private int current = 0;
    
  
    
 	// reverseTopo is not necessarily a topological order, it should be reverse
    
 	// post order instead
    
 	public KosarajuSCC(Digraph digraph, Iterable<Integer> reverseTopo) {
    
 		this.digraph = digraph;
    
 		V = digraph.getV();
    
  
    
 		visited = new boolean[V];
    
 		components = new int[V];
    
  
    
 		for (int v : reverseTopo) {
    
 			if (!visited[v]) {
    
 				dfs(v);
    
 				current++;
    
 			}
    
 		}
    
 	}
    
  
    
 	private void dfs(int v) {
    
 		visited[v] = true;
    
 		components[v] = current;
    
  
    
 		for (int w : digraph.adj(v)) {
    
 			if (!visited[w]) {
    
 				dfs(w);
    
 			}
    
 		}
    
 	}
    
  
    
 	public int[] getComponents() {
    
 		return components;
    
 	}
    
  
    
 	public List<List<Integer>> getSccs() {
    
 		sccs = new ArrayList<List<Integer>>();
    
  
    
 		for (int i = 0; i < current; i++) {
    
 			sccs.add(new ArrayList<Integer>());
    
 		}
    
  
    
 		for (int i = 0; i < V; i++) {
    
 			sccs.get(components[i]).add(i);
    
 		}
    
  
    
 		return sccs;
    
 	}
    
 }

下面对这个算法的正确性进行证明：(如果没有兴趣，可以直接略过 ：D)

证明的目标，就是最后一步 --- 每一颗搜索树代表的就是一个强连通分量

证明：设在图GR中，调用DFS(s)能够到达顶点v，那么顶点s和v是强连通的。

两个互相可达顶点之间必定存在一条单向路径。这是因为深度优先搜索（DFS）从顶点s出发必然能访问到顶点v。由此可知，在图G中必定存在一条从s到v的路径。关键在于证明在GR（生成树图）中也必定存在一条从v返回到s的路径。也就是说，在G中必须找到一条从s到v的回路。

这是因为，在对图G进行ReversePost-Order序列生成时，
s排在v前面。
这意味着，在构建该序列的过程中，
v是在s之后被加入进去的。
（这是因为使用栈作为数据结构时，
先加入的元素会在序列末尾）。
基于DFS操作的递归属性，
当处理节点v时，
在其所有子节点已经被完整处理完毕后才会返回。
满足该条件的情况有两种

1. DFS(v) START -> DFS(v) END -> DFS(s) START -> DFS(s) END

2. DFS(s) START -> DFS(v) START -> DFS(v) END -> DFS(s) END

基于当前已知的信息，在图GR中存在一条从顶点s指向顶点v的路径，则这表明图G中也包含从顶点v指向顶点s的一条路径。然而，在第一种情况下, 调用DFS(v)后无法在返回前再次调用DFS(s)，这与图G中存在的从v到s的一条路径相矛盾, 因此这种调用方式不可行。因而只有第二种情况符合逻辑。进一步可知, 通过DFS(s)开始并随后启动DFS(v), 我们能够确定从顶点s到顶点v必定有一条通路。

所以从s到v以及v到s都有路径可达，证明完毕。

复杂度分析：

基于上述对Kosaraju算法关键步骤的总结, 由此可见该算法要求对图进行两次深度优先搜索(DFS)操作, 并伴随一次图的转置操作. 因此, 其时间复杂度为O(V+E)