圖的連通性問題

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

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

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

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

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

if(i==m)continue;//不考慮第m個(gè)頂點(diǎn)

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

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