【概念】

1.割點

1）割點：刪除某點后，整個圖變?yōu)椴贿B通的兩個部分的點

2）割點集合：在一個無向圖中刪除該集合中的所有點，能使原圖變成互不相連的連通塊的點的集合

3）點連通度：最小割點集合點數

如上圖，若去掉 0，則圖被分成 12?和 34 兩個連通分量；若去掉 3，則圖被分成 012 和 4 兩個連通分量。

故：0、3 是割點，兩者是一個割點集，點連通度是 2

2.橋

1）橋（割邊）：刪除某邊后，使得連通圖變?yōu)椴贿B通的圖，一圖中可能有多條割邊

2）割邊集合：所有割邊的集合

3）邊連通度：最小割邊集合邊數

如上圖，去掉 5-6，2-5 后不再連通，圖被分為 1234、5、6 三個連通分量

故：5-6、2-5 是割邊，兩者組成的集是割邊集，邊連通度是 2

【原理】

1.求割點

對于一棵?DFS 搜索樹：

1）根結點：當且僅當根節(jié)點至少有兩個兒子時，其是割點

2）其他點：對于其他點 v，當僅有一個兒子 u 時，從 u 或 u 的后代出發(fā)，沒有指向 v 祖先(不含 v)的邊，則刪除 v后，u 和 v 的父親不連通時，v 是割點

2.求橋

對于邊 (u,v)，若發(fā)現 v 和它的后代不存在一條連接 u 或其祖先的邊，則刪除 (u,v) 后 u 和 v 不連通，因此邊 (u,v) 為橋

【過程】

1.求割點

1）對圖進行 Tarjan 算法，得到 dfn 和 low 兩個數組

2）每遍歷一個新的 u 的兒子 v 都記錄個數

3）low[u] 值更新后進行以下判斷（前提：v 未被遍歷）：

? ? ① u 為樹根，且兒子個數大于 1

? ? ②?u 不為樹根，但 low[v]>=dfn[u]

? ? 滿足以上任意條件 u 便為割點，記錄在一數組里，Tarjan 完成后再輸出即可（中途輸出會重復）

2.求橋

判斷原則：若 low[v]>dfn[u]，則 (u,v) 為割邊。

由于有的圖有重邊，因此不好通過上述判斷原則來處理，故使用以下方法：

1）對圖進行 Tarjan 算法，得到 dfn 和 low 兩個數組

2）形參加上 father，作用為記錄 u 的父親節(jié)點，避免在遍歷 v 時遇到重邊重新更新 low[u]

3）在 v 已被遍歷的位置加上判斷：如果 v 點等于 father，那么就不更新 low[u] 值

4）Tarjan算法結束后，遍歷所有節(jié)點u及其子節(jié)點v，如果 low[u]==low[v]，那么這條邊就為割邊

【實現】

1.先將數據保存下來，再求割點與橋

int n,m; int low[N],dfn[N]; vector<int>G[N]; bool is_cut[N];//記錄是否為割點 int father[N]; int tim;//時間戳 void Tarjan(int x,int pre){father[x]=pre;//記錄每一個點的父親dfn[x]=low[x]=tim++;//每找到一個新點，紀錄當前節(jié)點的時間戳for(int i=0;i<G[x].size();i++){int y=G[x][i];//當前結點的下一結點if(dfn[y]==-1){//若未被訪問過Tarjan(y,x);low[x]=min(low[x],low[y]);}else if(pre!=y)//假如k是i的父親的話，那么這就是無向邊中的重邊，有重邊那么一定不是橋low[x]=min(low[x],dfn[y]);//可能dfn[k]！=low[k]，所以不能用low[k]代替dfn[k],否則會上翻過頭} }int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;++i){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}tim=0;memset(low,-1,sizeof(low));memset(dfn,-1,sizeof(dfn));memset(father,0,sizeof(father));memset(is_cut,false,sizeof(is_cut));Tarjan(1,0);//先Tarjan求出dfn和low數組int root=0;for(int i=2;i<=n;i++){//統計根節(jié)點子樹的個數，根節(jié)點的子樹個數>=2,即為割點int temp=father[i];if(temp==1)root++;else{if(low[i]>=dfn[temp])//割點的條件is_cut[temp]=true;}}if(root>1)is_cut[1]=true;//打印割點for(int i=1;i<=n;++i)if(is_cut[i])printf("%d ",i);printf("\n");for(int i=1;i<=n;++i){int temp=father[i];if(temp>0&&low[i]>dfn[temp])//橋的條件printf("%d,%d\n",temp,i);}return 0; }

2.在 Tarjan 的過程中求橋

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 1000000+5; const int dx[] = {-1,1,0,0}; const int dy[] = {0,0,-1,1}; using namespace std;struct Edge{int from,to,next;int cut;//記錄該邊是否為橋Edge(){}Edge(int from,int to,int next,int cut):from(from),to(to),next(next),cut(cut){} }edge[N]; int n,m; int head[N],edgeNum; int dfn[N],low[N]; int block_cnt; void addEdge(int from,int to){//添邊edge[edgeNum]=Edge(from,to,head[from],false);head[from]=edgeNum++; } void tarjin(int x,int father){low[x]=dfn[x]=++block_cnt;for(int i=head[x];i!=-1;i=edge[i].next){int y=edge[i].to;if(!dfn[y]){tarjin(y,x);if(low[x]>low[y])low[x]=low[y];if(low[y]>dfn[x])edge[i].cut=true;}else if(y!=father)low[x]=min(low[x],dfn[y]);} } int main(){scanf("%d%d",&n,&m);memset(dfn,0,sizeof(dfn));memset(head,-1,sizeof(head));edgeNum=0;while(m--){int x,y;scanf("%d%d",&x,&y);addEdge(x,y);addEdge(y,x);}tarjin(1,1); for(int i=0;i<edgeNum;i++)//打印橋if(edge[i].cut)printf("%d %d\n",edge[i].from,edge[i].to);return 0; }

總結

以上是生活随笔為你收集整理的图论 —— 图的连通性 —— Tarjan 求割点与桥的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。