圖的連通性問題

第8章圖的連通性問題連通性初步Question：如果一個無向圖是非連通圖，從某個頂點出發(fā)，能否遍歷到所有的頂點？Answer：對非連通圖，從某個頂點出發(fā)進(jìn)行遍歷，只能遍歷到它所在的連通子圖上的所有頂點。依次從每個未訪問過的頂點出發(fā)進(jìn)行遍歷，就可以遍歷完所有的頂點，并且可以得到非連通圖的連通分量個數(shù)。//從頂點n出發(fā)，DFS遍歷intDFS(intn){visited[n]=1;for(inti=1;i<=nodes;i++){if(node[n][i]==1&&!visited[i])DFS(i);}return0;}//依次從每個未訪問過的頂點//出發(fā)DFSsubnets=0;for(intn=1;n<=nodes;n++){

if(!visited[n]){DFS(n);subnets++;}}關(guān)節(jié)點及重連通圖0123456789關(guān)節(jié)點：在一個無向連通圖G中，當(dāng)且僅當(dāng)刪去G中的頂點v及其所關(guān)聯(lián)的邊后，可將圖分割成2個或2個以上的連通分量，則稱頂點v為關(guān)節(jié)點(ArticulationPoint)，或者稱為割頂。圖(1)中，頂點1、3、5、7都是關(guān)節(jié)點重連通圖：沒有關(guān)節(jié)點的連通圖。在重連通圖上，任何一對頂點之間至少存在有2條路徑，在刪去某個頂點及其所關(guān)聯(lián)的邊時，也不破壞圖的連通性。重連通分量如果連通圖G不是重連通圖，那么它可以包括幾個重連通分量。一個連通圖的重連通分量是該圖的極大連通子圖。圖(1)包含了6個連通分量0123456789177判斷關(guān)節(jié)點的樸素方法依次去掉每個頂點（及其所關(guān)聯(lián)的邊），然后用DFS去搜索整個圖，可得到該圖的連通分量的個數(shù)，如果是大于2，則該頂點是關(guān)節(jié)點。(這種方法復(fù)雜度很高，只適合規(guī)模較小的題目)例子：ZOJ1311//依次去掉每個頂點(及其所關(guān)聯(lián)的邊)，用DFS遍歷剩下的子圖，得連通分量個數(shù)for(intm=1;m<=nodes;m++){

intsubnets=0;//子網(wǎng)數(shù)目 memset(visited,0,sizeof(visited));

for(intn=1;n<=nodes;n++){

if(m==n)continue;//跳過頂點n(并不需要真正去掉頂點n)

if(!visited[n]){ DFS(m,n);//去掉頂點m，從頂點n出發(fā)DFS subnets++; } }

if(subnets>1)SPF++;}//去掉第m個頂點及其所關(guān)聯(lián)的邊，從第n個頂點出發(fā)進(jìn)行DFSintDFS(intm,intn){ visited[n]=1;

for(inti=1;i<=nodes;i++) {

if(i==m)continue;//不考慮第m個頂點

if(node[n][i]==1&&!visited[i]) DFS(m,i); }

return0;}從頂點3出發(fā)進(jìn)行深度優(yōu)先搜索，得到圖(b)所示的生成樹，并改畫成圖(c)所示的樹形形狀。圖(c)中每個頂點外側(cè)的數(shù)字標(biāo)明了進(jìn)行深度優(yōu)先搜索時各頂點訪問的次序，稱為頂點的深度優(yōu)先數(shù)，可以記在數(shù)組dfn中。0123456789(a)0123456789(b)1234510987601234(c)1234510987697658求關(guān)節(jié)點的算法注意：如果u和v是2個頂點，且在深度優(yōu)先搜索生成樹中u是v的祖先，則有dfn[u]<dfn[v]，表明u的深度優(yōu)先數(shù)小于v，u先于v被訪問。01234(c)1234510987697658回邊與交叉邊回邊：當(dāng)且僅當(dāng)u在生成樹中是v的祖先，或者v是u的祖先，非生成樹的邊(u,v)才成為一條回邊。如圖(a)中的(1,3)、(5,7)都是回邊。交叉邊：除生成樹的邊、回邊外，原圖中的其他邊稱為交叉邊。一旦生成樹確定以后，那么原圖中的邊只可能有回邊和生成樹的邊，交叉邊實際上是不存在的。為什么？假設(shè)圖(a)中存在邊(1,7)(這就是所謂的交叉邊)，那么頂點7(甚至其他頂點都)只能位于頂點3的左邊這條子樹中。0123456789(a)01234(c)1234510987697658頂點u是關(guān)節(jié)點的充要條件：如果頂點u是深度優(yōu)先搜索生成樹的根，則u至少有2個子女；為什么？刪除u，它的子女所在的子樹就斷開了，你不用擔(dān)心這些子樹之間(在原圖中)可能存在邊，因為交叉邊是不存在的。如果u不是生成樹的根，則它至少有一個子女w，從w出發(fā)，不可能通過w、w的子孫，以及一條回邊組成的路徑到達(dá)u的祖先。(這時刪去頂點u及其所關(guān)聯(lián)的邊，則以頂點w為根的子樹就從搜索樹中脫離了。)頂點5為什么是關(guān)節(jié)點？頂點6為什么不是關(guān)節(jié)點？0123456789(a)01234(c)1234510987697658因此，可對圖G的每個頂點u定義一個low值，low[u]是從u或u的子孫出發(fā)通過回邊可以到達(dá)的最低深度優(yōu)先數(shù)。Low[u]=Min{dfn[u],Min{low[w]|w是u的一個子女},min{dfn[v]|(u,v)是一條回邊}}因此，頂點u是關(guān)節(jié)點的充要條件是：u或者是具有兩個以上子女的一個生成樹的根，或者雖然不是一個根，但它有一個子女w，使得low[w]>=dfn[u]，這時w及其子孫不存在指向頂點u的祖先的回邊。(這時刪去頂點u及其所關(guān)聯(lián)的邊，則以頂點w為根的子樹就從搜索樹中脫離了。)頂點0123456789dfn54312678109low510low19low16low16low16第一棵子樹，回退順序：0,1,2,4,3第二棵子樹，回退順序：8,9,7,6,501234(c)1234510987697658在DFS的回退過程計算每個頂點的low值：Low[u]=Min{dfn[u],Min{low[w]|w是u的一個子女},min{dfn[v]|(u,v)是一條回邊} }在回退過程計算頂點的low值0123456789(a)前進(jìn)回退頂點0123456789dfn54312678109low510low19low16low16low16第一棵子樹,回退順序0,1,2,4,3第二棵子樹,回退順序8,9,7,6,5頂點u是關(guān)節(jié)點的充要條件：u是根，且有2個以上的子女u不是根，但存在一個子女w，使得low[w]>=dfn[u]01234(c)123