tarjan算法

一種由Robert Tarjan提出的求解有向圖強連通分量的線性時間的算法。

基本介紹

• 中文名：tarjan算法
• 外文名：tarjan's algorithm
• 性質：求有向圖強連通分量的算法
• 範圍：有向圖G中
• 目的：用來求有向圖的強連通分量

算法介紹

如果兩個頂點可以相互通達，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。

下圖中，子圖{1,2,3,4}為一個強連通分量，因為頂點1,2,3,4兩兩可達。{5},{6}也分別是兩個強連通分量。

Tarjan算法是用來求有向圖的強連通分量的。求有向圖的強連通分量的Tarjan算法是以其發明者Robert Tarjan命名的。Robert Tarjan還發明了求雙連通分量的Tarjan算法。

Tarjan算法是基於對圖深度優先搜尋的算法，每個強連通分量為搜尋樹中的一棵子樹。搜尋時，把當前搜尋樹中未處理的節點加入一個堆疊，回溯時可以判斷棧頂到棧中的節點是否為一個強連通分量。

定義DFN(u)為節點u搜尋的次序編號(時間戳)，Low(u)為u或u的子樹能夠追溯到的最早的棧中節點的次序號。

當DFN(u)=Low(u)時，以u為根的搜尋子樹上所有節點是一個強連通分量。

接下來是對算法流程的演示。

從節點1開始DFS，把遍歷到的節點加入棧中。搜尋到節點u=6時，DFN[6]=LOW[6]，找到了一個強連通分量。退棧到u=v為止，{6}為一個強連通分量。

返回節點5，發現DFN[5]=LOW[5]，退棧後{5}為一個強連通分量。

返回節點3，繼續搜尋到節點4，把4加入堆疊。發現節點4向節點1有後向邊，節點1還在棧中，所以LOW[4]=1。節點6已經出棧，(4,6)是橫叉邊，返回3，(3,4)為樹枝邊，所以LOW[3]=LOW[4]=1。

繼續回到節點1，最後訪問節點2。訪問邊(2,4)，4還在棧中，所以LOW[2]=DFN[4]=5。返回1後，發現DFN[1]=LOW[1]，把棧中節點全部取出，組成一個連通分量{1,3,4,2}。

至此，算法結束。經過該算法，求出了圖中全部的三個強連通分量{1,3,4,2},{5},{6}。

可以發現，運行Tarjan算法的過程中，每個頂點都被訪問了一次，且只進出了一次堆疊，每條邊也只被訪問了一次，所以該算法的時間複雜度為O(N+M)。

實例代碼

偽代碼

tarjan(u){    DFN[u]=Low[u]=++Index//為節點u設定次序編號和Low初值    Stack.push(u)//將節點u壓入棧中    for each(u,v) in E//枚舉每一條邊        if (visnotvisted)//如果節點v未被訪問過            tarjan(v)//繼續向下找            Low[u]=min(Low[u],Low[v])        else if (vinS)//如果節點v還在棧內                Low[u]=min(Low[u],DFN[v])    if (DFN[u]==Low[u])//如果節點u是強連通分量的根    repeat{        v=S.pop//將v退棧，為該強連通分量中一個頂點        printv        until(u==v)    }}

pascal代碼

procedure tarjan(x:longint);var i,j,k:longint;begin  inc(h);  dfn[x]:=h;low[x]:=h;//dfn，low初始化，記錄訪問該點的真實時間dfn和最早時間low  inc(t);  f[t]:=x;//當前元素入棧  s[x]:=true;ss[x]:=true;//s，ss標記  for i:=1 to 200 do  if p[x,i] then  begin//枚舉每一條邊    if not s[i] then    begin      tarjan(i);//如果節點i未被訪問過繼續向下找      low[x]:=min(low[x],low[i]);    end    else if ss[i] then low[x]:=min(low[x],dfn[i]);//如果節點i還在棧內  end;  if dfn[x]=low[x] then//如果s的最早訪問時間等於其實際訪問時間,則可把其視作迴路的"始點"  begin    inc(ans);//連通塊編號    while f[t+1]<>x do//將由x直接或間接擴展出的點標記為同一連通塊,標記訪問後出棧    begin      ss[f[t]]:=false;      dec(t);    end;  end;//如果節點x是強連通分量的根，退棧直到x的前一個數據，記錄這個強連通分量的數據end;

C++代碼

#define M 5010//題目中可能的最大點數int STACK[M],top=0;//Tarjan算法中的棧bool InStack[M];//檢查是否在棧中int DFN[M];//深度優先搜尋訪問次序int Low[M];//能追溯到的最早的次序int ComponentNumber=0;//有向圖強連通分量個數int Index=0;//索引號vector<int> Edge[M];//鄰接表表示vector<int> Component[M];//獲得強連通分量結果int InComponent[M];//記錄每個點在第幾號強連通分量里int ComponentDegree[M];//記錄每個強連通分量的度void Tarjan(int i){    int j;    DFN[i]=Low[i]=Index++;    InStack[i]=true;STACK[++top]=i;    for (int e=0;e<Edge[i].size();e++)    {        j=Edge[i][e];        if (DFN[j]==-1)        {            Tarjan(j);            Low[i]=min(Low[i],Low[j]);        }        else            if (InStack[j]) Low[i]=min(Low[i],DFN[j]);//也可Low[i]=min(Low[i],Low[j]);僅限在求強聯通分量時    }    if (DFN[i]==Low[i])    {        ComponentNumber++;        do{            j=STACK[top--];            InStack[j]=false;            Component[ComponentNumber].            push_back(j);            InComponent[j]=ComponentNumber;        }        while (j!=i);    }}