利用Tarjan算法求有向图的强连通分量

返回首页

Tarjan算法是用于求有向图的强连通分量

Tarjan算法的用途之一是，求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话，那么这个强连通分量就是极大强连通分量。

时间复杂度：O（M+N） 注：M代表边数，N代表顶点数。

步骤概要：

步骤1: 找一个没有被遍历过的顶点v，进行步骤2（v）（遍历时间由1开始累加，若是非连通图，则须重复进行步骤1）。否则，算法结束。

步骤2（v）: 初始化dfn[v]和low[v]的值为当前的遍历时间，并且v进栈；

对于v所有的邻接顶点u：
（1） 如果u没有被遍历过，则进行步骤2（u），同时维护low[v]。
（2） 如果u已经被遍历过，但还在栈中（即还不属于任一强连通分量），则维护low[v]，否则不做任何操作。
　　 如果有dfn[v]==low[v]，则把栈中的顶点弹出（直到把v都弹出为止），这些顶点组成一个强连通分量。

简要证明:

1． 在栈里，当dfs遍历到v，而且已经遍历完v所能直接到达的顶点时，low[v]=dfn[v]时，v一定能到达栈里v上面的顶点：
因为当dfs遍历到v，而且已经dfs递归调用完v所能直接到达的顶点时（假设上面没有low=dfn），这时如果发现low[v]=dfn[v]，栈上面的顶点一定是刚才从顶点v递归调用时进栈的，所以v一定能够到达那些顶点。

2 .dfs遍历时，如果已经遍历完v所能直接到达的顶点而low[v]=dfn[v]，我们知道v一定能到达栈里v上面的顶点，这些顶点的low一定小于 自己的dfn，不然就会出栈了，也不会小于dfn[v],不然low [v]一定小于dfn[v],所以栈里v以其v以上的顶点组成的子图是一个强连通分量，如果它不是极大强连通分量的话low[v]也一定小于dfn[v]（这里不再详细说），所以栈里v以其v以上的顶点组成的子图是一个极大强连通分量。
强烈推荐详细的解释与说明

显示的是一个随机 12 * 12 的方阵

计算出来后的