tarjan算法

tarjan算法

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

基本介紹

算法介紹,實例代碼,偽代碼,pascal代碼,C++代碼,

算法介紹

如果兩個頂點可以相互通達,則稱兩個頂點強連通(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}為一個強連通分量。
tarjan算法
返回節點5,發現DFN[5]=LOW[5],退棧後{5}為一個強連通分量
tarjan算法
返回節點3,繼續搜尋到節點4,把4加入堆疊。發現節點4向節點1有後向邊,節點1還在棧中,所以LOW[4]=1。節點6已經出棧,(4,6)是橫叉邊,返回3,(3,4)為樹枝邊,所以LOW[3]=LOW[4]=1。
tarjan算法
繼續回到節點1,最後訪問節點2。訪問邊(2,4),4還在棧中,所以LOW[2]=DFN[4]=5。返回1後,發現DFN[1]=LOW[1],把棧中節點全部取出,組成一個連通分量{1,3,4,2}。
tarjan算法
至此,算法結束。經過該算法,求出了圖中全部的三個強連通分量{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);    }}

相關詞條

熱門詞條

聯絡我們