http://blog.csdn.net/cicirise/archive/2009/04/13/4068611.aspx

?

最近在做圓桌騎士的問題，在一個無向圖中求出雙連通分量，判斷各雙連通分量中是否含有奇圈，求出不能構成奇圈的節點的個數。思路大概明確了，但是寫的時候老是出現問題，所以專題又看了一下雙連通分量的算法，看來看去，還是劉汝佳的最經典，索性直接手打出來，方便以后再看

void DFS(節點編號k,k的父親節點編號father,deep)
{
int i,tot;
染色C_k=灰色；
D_k=deep記錄頂點k在樹中的深度。
//Ancestot_k=deep,tot=0;
for(int i=1;i<=n;i++)
{
If（(節點j和k相連)&&（i！=father）&&C_i==灰色）
? Ancestor_k=MIN（Ancestor_k,D_i）;
If（(節點i和k相連)&&（C_i==白色））
{
? DFS（i，k，deep+1）；
? tot++;
? Ancestor_k=MIN(Ancestot_k,Ancestor_i);
? if((k==root&&tot>1)||(k!=root&&Ancestor_i>=D_k)
? cut_k=true;
? if(Ancesot_i>D_k)
? bridge_i,k=true;
}
}
染色C_k=黑色；
}
DFS遍歷本身查找除了連通塊外并沒有多大用途，關鍵是遍歷的同時，可以記下很多有用的信息。下面來看看哪些是與DFS相關的常用信息：
無向連通圖的割頂 我們先考慮割頂的性質
? 考慮根頂點root。如果頂點x和y同時root的兒子，那么由此證明x無法通過非root的頂點與y相連，所以當根root有數量>1的兒子時，根是圖的割頂。
? 考慮非根頂點，再考慮i的某個兒子節點j。易知：
1. 和j相連的白色節點丟將成為j的子孫。
2. 和j相連的灰色節點都是j的祖先，由j指向i祖先的邊稱為后向邊。
3. 黑色節點不可能與j相連。
如果i和j的子孫都不存在指向i祖先的后向邊，那么刪除頂點i后，頂點j和i的祖先或者兄弟將無法連通。因此，當且僅當i的某個兒子及兒子的子孫均沒有指向i祖先的后向邊是，i是圖的割頂。
割頂的求法 在DFS框架的基礎上增加Ancestor_k和tot值的計算。
Ancestor_k記錄和k以及k的子孫相連的輩分最高的祖先，當Ancestor_j<D_j（j是i的兒子）時j和j的子孫存在指向i祖先的后向邊。Tot便是頂點k的兒子的數量。注意，根與非根頂點要注意區別對待。
Cut_k=true表示頂點k為圖的割頂
無向連通圖的橋 如果y是x的兒子并且Ancestor_y>D_x(注意不是Ancestor_y>=D_x)，那么刪除邊（x,y）后，頂點y將與x不連通，所以（x,y）是圖的橋
橋的求法 他也是基于DFS的框架的算法，Bridge_k,i=true表示記錄邊（i，k）為圖的橋

轉載于:https://www.cnblogs.com/ZJoy/archive/2011/05/12/2044671.html

總結

以上是生活随笔為你收集整理的割点和桥算法——摘自《算法艺术与信息学竞赛》的全部內容，希望文章能夠幫你解決所遇到的問題。

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