摘要：在實(shí)際的測(cè)試中，算法的運(yùn)行效率也比算法高左右。此外，該算法與求無向圖的雙連通分量割點(diǎn)橋的算法也有著很深的聯(lián)系。學(xué)習(xí)該算法，也有助于深入理解求雙連通分量的算法，兩者可以類比組合理解。固屬于同一連通分支。

參考資料
http://blog.csdn.net/acmmmm/a...
https://www.byvoid.com/blog/s...
http://blog.csdn.net/nothi/ar...

在教材中有向圖的強(qiáng)連通只提及了一種，其實(shí)還有另外兩個(gè)經(jīng)典的算法，因此做一個(gè)補(bǔ)充。

tarjan的過程就是dfs過程

對(duì)圖dfs一下，遍歷所有未遍歷過的點(diǎn) ，會(huì)得到一個(gè)有向樹，顯然有向樹是沒有環(huán)的。

（注意搜過的點(diǎn)不會(huì)再搜） 則能產(chǎn)生環(huán)的只有 指向已經(jīng)遍歷過的點(diǎn) 的邊

只有紅色與綠色邊有可能產(chǎn)生環(huán)。
對(duì)于深搜過程，我們需要一個(gè)棧來保存當(dāng)前所在路徑上的所有點(diǎn)（棧中所有點(diǎn)一定是有父子關(guān)系的）
再仔細(xì)觀察紅邊與綠邊，首先得到結(jié)論：紅邊不產(chǎn)生環(huán)，綠邊產(chǎn)生環(huán)

對(duì)于紅邊，連接的兩個(gè)點(diǎn)3、7沒有父子關(guān)系，這種邊稱為橫叉邊。
橫叉邊一定不產(chǎn)生環(huán)。

對(duì)于綠邊，連接的兩個(gè)點(diǎn)6、4是父子關(guān)系，這種邊稱為后向邊。
環(huán)一定由后向邊產(chǎn)生。

圖中除了黑色的樹枝邊，一定只有橫叉邊和后向邊（不存在其他種類的邊）

則以下考慮對(duì)于這兩種邊的處理和判斷：

Stack = {1,2,3}。3沒有多余的其他邊，因此3退棧，把3作為一個(gè)強(qiáng)連通分量

再次深搜：

此時(shí)棧 Stack = {1,2,7}
發(fā)現(xiàn)紅邊指向了已經(jīng)遍歷過的點(diǎn)3 => 是上述的2種邊之一
而3不在棧中
=> 3點(diǎn)與7點(diǎn)無父子關(guān)系
=> 該邊為橫叉邊
=> 采取無視法。

繼而7點(diǎn)退棧 產(chǎn)生連通分量{7}
繼而2點(diǎn)退棧 產(chǎn)生連通分量{2}

再次深搜：

此時(shí) Stack = {1,4,5,6}
發(fā)現(xiàn)綠邊指向了已經(jīng)遍歷過的點(diǎn)4 => 是上述的2種邊之一
而4在棧中
=> 4點(diǎn)與6點(diǎn)是父子關(guān)系
=> 該邊為后向邊
=> 4->6的路徑上的點(diǎn)都是環(huán)。

實(shí)際情況可能更復(fù)雜：

出現(xiàn)了大環(huán)套小環(huán)的情況，顯然我們認(rèn)為最大環(huán)是一個(gè)強(qiáng)連通分量(即:{4,5,6,8} ）

因而我們需要強(qiáng)化一下dfs過程，增添幾個(gè)變量來記錄父節(jié)點(diǎn)和后向邊的情況

定義：

int dfn[N], low[N];

dfn[i] 表示 遍歷到 i 點(diǎn)時(shí)是第幾次dfs （有時(shí)也叫時(shí)間戳）

low[u] 表示 u 的子樹 能連接到 [棧中] 最上端的點(diǎn) 的dfn值(換句話說，也就是最小的dfn）

Stack stack 上述的棧
int BelongTo[N] 強(qiáng)連通分量的ID

通俗語言解讀：

dfn[i] 即我就是我，是數(shù)字不一樣的煙火。每個(gè)點(diǎn)的ID（不是強(qiáng)連通分量的ID，而是每個(gè)點(diǎn)自己的身份標(biāo)識(shí)ID），按時(shí)間順序賦值。比如第一個(gè)尋訪的dfn的值為 1，第二個(gè)尋訪的DFN的值為 2，以此類推?？梢酝ㄟ^比較大小來判斷是爸爸還是兒子。（是后向邊還是橫插邊？）

low[u] 如果是后向邊的話連到哪個(gè)爸爸？記錄下來爸爸的ID。

Stack 怎么判斷是不是后向邊呢？—>看在不在棧內(nèi)。

Tarjan算法是基于對(duì)圖深度優(yōu)先搜索的算法，每個(gè)強(qiáng)連通分量為搜索樹中的一棵子樹。
搜索時(shí)，把當(dāng)前搜索樹中未處理的節(jié)點(diǎn)加入一個(gè)堆棧，回溯時(shí)可以判斷棧頂?shù)綏Ｖ械墓?jié)點(diǎn)是否為一個(gè)強(qiáng)連通分量。

定義dfn(u)為節(jié)點(diǎn)u搜索的次序編號(hào)(時(shí)間戳)；
Low(u)為u或u的子樹能夠追溯到的最早的棧中節(jié)點(diǎn)的次序號(hào)。

由定義可以得出，

low(u)=min
{
    dfn(u),
    low(v),(u,v)為樹枝邊，u為v的父節(jié)點(diǎn) //回溯時(shí)用
    dfn(v),(u,v)為指向棧中節(jié)點(diǎn)的后向邊(非橫叉邊) // 已訪問過時(shí)用。沒有想明白為什么是dfn(v)而不是low(v)?????????
}

當(dāng)dfn(u)==low(u)時(shí)，以u(píng)為根的搜索子樹上所有節(jié)點(diǎn)是一個(gè)強(qiáng)連通分量。

原因

在算法開始的時(shí)候，我們把 i 圧入棧中。根據(jù) low[i] 和 dfn[i] 的定義我們知道，

如果 low[i] < dfn[i]，則以 i 為頂點(diǎn)的子樹中，有指向祖先的后向邊，則說明 i 和 i 的父親為在同一連通分支，也就是說留在棧中的元素都是和父結(jié)點(diǎn)在同一連通分支的。

如果 low[i] == dfn[i]，則 i 為頂點(diǎn)的子樹中沒有后向邊，那么由于 留在棧中的元素都是和父結(jié)點(diǎn)在同一連通分支的，我們可以知道，從棧頂?shù)皆?i 構(gòu)成了一個(gè)連通分支。顯然，low[i]不可能小于dfn[i]

算法偽代碼如下

tarjan(u)
{
    dfn[u]=low[u]=++index                      // 為節(jié)點(diǎn)u設(shè)定次序編號(hào)和low初值
    stack.push(u)                              // 將節(jié)點(diǎn)u壓入棧中
    for each (u, v) in E                       // 枚舉每一條邊
        if (v is not visted)               // 如果節(jié)點(diǎn)v未被訪問過
            tarjan(v)                  // 繼續(xù)向下找
            Low[u] = min(low[u], low[v])
        else if (v in stack)                   // 如果節(jié)點(diǎn)v還在棧內(nèi)
            Low[u] = min(low[u], dfn[v])
    if (dfn[u] == low[u])                      // 如果節(jié)點(diǎn)u是強(qiáng)連通分量的根
        repeat
            v = stack.pop                  // 將v退棧，為該強(qiáng)連通分量中一個(gè)頂點(diǎn)
            print v
        until (u== v)
}

復(fù)雜度

時(shí)間：O(N+M)

與Trajan算法相比，Kosaraju算法可能會(huì)稍微更直觀一些。但是Tarjan只用對(duì)原圖進(jìn)行一次DFS，不用建立逆圖，更簡(jiǎn)潔。在實(shí)際的測(cè)試中，Tarjan算法的運(yùn)行效率也比Kosaraju算法高30%左右。此外，該Tarjan算法與求無向圖的雙連通分量(割點(diǎn)、橋)的Tarjan算法也有著很深的聯(lián)系。學(xué)習(xí)該Tarjan算法，也有助于深入理解求雙連通分量的Tarjan算法，兩者可以類比、組合理解。

public class Tarjan {
    private int[] id; // 強(qiáng)連通ID
    private int index_id = 0; // 強(qiáng)連通ID計(jì)數(shù)器
    private int[] dfn, low; //時(shí)間戳計(jì)數(shù)器
    private int index_dfn = 1; //時(shí)間戳初始化時(shí)默認(rèn)為0。因此從1開始賦值，以區(qū)別是否訪問過。
    private Stack stack= new Stack();
    private boolean[] onStack;
    
    public Tarjan(Digraph G) {
        onStack = new boolean[G.V()];
        id = new int[G.V()];
        dfn = new int[G.V()];
        low = new int[G.V()];

        for (int s = 0; s < G.V(); s++)
            if (dfn[s]==0) {
                tarjan(G, s);
                index_id++;
            }
    }

    private void tarjan(Digraph G, int u) {
        stack.push(u); //壓入棧
        onStack[u] = true; //方便之后判斷
        dfn[u] = low[u] = ++index_dfn; //時(shí)間戳賦值，并表示訪問過了
        for (int w : G.adj(u)) {
            if (dfn[w] == 0) { //若w未被訪問過
                tarjan(G, w); //繼續(xù)深搜
                low[u] = Math.min(low[w], low[u]); //回溯，當(dāng)前點(diǎn)u 選取包括自己的子樹中最小的low值
            } else if (onStack[w] && dfn[w]
簡(jiǎn)單證明
首先，這邊再重復(fù)一下什么是后向邊：就是在深度優(yōu)先搜索中，子孫指向祖先的邊。
在一棵深度優(yōu)先搜索樹中，對(duì)于結(jié)點(diǎn)v, 和其父親結(jié)點(diǎn)u而言，u,v 屬于同一個(gè)強(qiáng)連通分支的充分必要條件是  
以ｖ為根的子樹中，有一條后向邊指向u或者u的祖先。
1、必要性
如果 u, v 屬于同一個(gè)強(qiáng)連通分支則必定存在一條 u -> v 的路徑和一條 v -> u的路徑。
合并兩條則有 u->v->v1->v2->..vn->u, 若頂點(diǎn)v1到vn都是v 的子孫,則有 vn->u這樣一條后向邊。
如果v1到vn 不全是vn的子孫，則必定有一個(gè)是u的祖先，我們不妨設(shè)vi為u的祖先，則有一條后向邊 V[i-1] ->v[i]。
2、充分性
我們?cè)O(shè) u1->u2->u3..->un->u->v->v1->v2..->vn。
我們假設(shè)后向邊vn指向ui則有這樣一個(gè)環(huán)：u[i]->u[i+1]...->u->v->v1->v2..->v[n-1]->v[n]->u[i]。
易知，有一條u->v的路徑，同時(shí)有v->u的路徑。固u,v屬于同一連通分支。