【概述】

Tarjan 算法是基于對(duì)圖深度優(yōu)先搜索的算法，每個(gè)強(qiáng)連通分量為搜索樹(shù)中的一棵子樹(shù)。

搜索時(shí)，把當(dāng)前搜索樹(shù)中未處理的節(jié)點(diǎn)加入一個(gè)堆棧，回溯時(shí)可以判斷棧頂?shù)綏Ｖ械墓?jié)點(diǎn)是否為一個(gè)強(qiáng)連通分量。

【基本思路】

定義 DFN(u) 為節(jié)點(diǎn) u 搜索的次序編號(hào)（時(shí)間戳），即是第幾個(gè)被搜索到的，Low(u) 為 u 或 u 的子樹(shù)能夠追溯到的最早的棧中節(jié)點(diǎn)的次序號(hào)。

每次找到一個(gè)新點(diǎn) i，有：DFN(i)=low(i)

當(dāng)點(diǎn) u?與點(diǎn) v 相連時(shí)，如果此時(shí)（時(shí)間為 DFN[u] 時(shí)）v不在棧中，u 的 low 值為兩點(diǎn)的 low 值中較小的一個(gè)

即：low[u]=min(low[u],low[v])

當(dāng)點(diǎn) u 與點(diǎn) v 相連時(shí)，如果此時(shí)（時(shí)間為 DFN[u] 時(shí)）v 在棧中，u 的 low 值為 u 的 low 值和 v 的 dfn 值中較小的一個(gè)

即：low[u]=min(low[u],dfn[v])?

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

【流程】

以下圖為例，共有三個(gè)強(qiáng)連通分量：1234、5、6

從節(jié)點(diǎn) 1 開(kāi)始 DFS，把遍歷到的節(jié)點(diǎn)加入棧中，搜索到節(jié)點(diǎn) u=6 時(shí)，DFN[6]=LOW[6]=4，找到了一個(gè)強(qiáng)連通分量 {6}

返回節(jié)點(diǎn) 5，發(fā)現(xiàn) DFN[5]=LOW[5]=3，退棧后 {5} 為一個(gè)強(qiáng)連通分量。

返回節(jié)點(diǎn) 3，繼續(xù)搜索到節(jié)點(diǎn) 4，把 4 加入堆棧。發(fā)現(xiàn)節(jié)點(diǎn) 4 像節(jié)點(diǎn) 1 的后向邊，節(jié)點(diǎn) 1 還在棧中，所以 LOW[4]=1。節(jié)點(diǎn) 6 已經(jīng)出棧，不再訪問(wèn) 6，返回 3，(3,4) 為樹(shù)枝邊，所以 LOW[3]=LOW[4]=1。

繼續(xù)回到節(jié)點(diǎn) 1，最后訪問(wèn)節(jié)點(diǎn) 2。訪問(wèn)邊 (2,4)，4 還在棧中，所以 LOW[2]=4。返回 1 后，發(fā)現(xiàn) DFN[1]=LOW[1]，把棧中節(jié)點(diǎn)全部取出，組成一個(gè)連通分量 {1,3,4,2}。

至此，算法結(jié)束。經(jīng)過(guò)該算法，求出了圖中全部的三個(gè)強(qiáng)連通分量{1,3,4,2}、{5}、{6}。

【時(shí)間復(fù)雜度】

通過(guò)上述流程分析，運(yùn)行 Tarjan 算法的過(guò)程中，每個(gè)頂點(diǎn)都被訪問(wèn)了一次，且只進(jìn)出了一次堆棧，每條邊也只被訪問(wèn)了一次，所以該算法的時(shí)間復(fù)雜度為 O(N+M)。

【實(shí)現(xiàn)】

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<vector> #define N 20001 using namespace std; int n,m; vector<int> G[N]; stack<int> S; int dfn[N],low[N]; bool vis[N];//標(biāo)記數(shù)組 int sccno[N];//記錄結(jié)點(diǎn)i屬于哪個(gè)強(qiáng)連通分量 int block_cnt;//時(shí)間戳 int sig;//記錄強(qiáng)連通分量個(gè)數(shù) void Tarjan(int x){vis[x]=true;dfn[x]=low[x]=++block_cnt;//每找到一個(gè)新點(diǎn)，紀(jì)錄當(dāng)前節(jié)點(diǎn)的時(shí)間戳S.push(x);//當(dāng)前結(jié)點(diǎn)入棧for(int i=0;i<G[x].size();i++){//遍歷整個(gè)棧int y=G[x][i];//當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)if(vis[y]==false){//若未被訪問(wèn)過(guò)Tarjan(y);low[x]=min(low[x],low[y]);}else if(!sccno[y])//若已被訪問(wèn)過(guò)，且不屬于任何一個(gè)連通分量low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){//滿足強(qiáng)連通分量要求sig++;//記錄強(qiáng)連通分量個(gè)數(shù)while(true){//記錄元素屬于第幾個(gè)強(qiáng)連通分量int temp=S.top();S.pop();sccno[temp]=sig;if(temp==x)break;}} } int main() {while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)G[i].clear();while(m--){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);}sig=0;block_cnt=0;memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(sccno,0,sizeof(sccno));for(int i=0;i<n;i++)if(vis[i]==false)Tarjan(i);for(int i=0;i<n;i++)printf("%d號(hào)點(diǎn)屬于%d分量\n",i,sccno[i]);} }

總結(jié)

以上是生活随笔為你收集整理的图论 —— 图的连通性 —— Tarjan 求强连通分量的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。