複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/tarjan算法/10687825
複製
複製成功

tarjan算法

鎖定
一種由Robert Tarjan提出的求解有向圖強連通分量的線性時間的算法。
中文名
tarjan算法
外文名
tarjan's algorithm
性    質
求有向圖強連通分量的算法
範    圍
有向圖G中
目    的
用來求有向圖的強連通分量

目錄

  1. 1 算法介紹
  2. 2 實例代碼
  3. ▪ 偽代碼
  4. ▪ pascal代碼
  5. ▪ C++代碼

tarjan算法算法介紹

如果兩個頂點可以相互通達，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。
圖1中，子圖{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}為一個強連通分量。
圖1 圖1
返回節點5，發現DFN[5]=LOW[5]，退棧後{5}為一個強連通分量。
tarjan算法 tarjan算法
返回節點3，繼續搜索到節點4，把4加入堆棧。發現節點4向節點1有後向邊，節點1還在棧中，所以LOW[4]=1。節點6已經出棧，(4,6)是橫叉邊，返回3，(3,4)為樹枝邊，所以LOW[3]=LOW[4]=1。
tarjan算法 tarjan算法
圖2 圖2
繼續回到節點1，最後訪問節點2。訪問邊(2,4)，4還在棧中，所以LOW[2]=DFN[4]=5。返回1後，發現DFN[1]=LOW[1]，把棧中節點全部取出，組成一個連通分量{1,3,4,2}。
至此，算法結束。經過該算法，求出了圖2中全部的三個強連通分量{1,3,4,2},{5},{6}。
可以發現，運行Tarjan算法的過程中，每個頂點都被訪問了一次，且只進出了一次堆棧，每條邊也只被訪問了一次，所以該算法的時間複雜度為O(N+M)。

tarjan算法實例代碼

tarjan算法偽代碼

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)
    }
}

tarjan算法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;

tarjan算法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);
    }
}