圖的連通性問題

1、信息學(xué)院信息技術(shù)教研室VsVtV2V4V3V12484279146V1V8V9V10V7V4V3V6V5V2王桂平王桂平第第8 8章章 圖的連通性問題圖的連通性問題2連通性初步如果一個(gè)無向圖是非連通圖，從某個(gè)頂點(diǎn)出發(fā)，能否遍歷到所有的頂點(diǎn)？對非連通圖，從某個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷，只能遍歷到它所在的連通子圖上的所有頂點(diǎn)。依次從每個(gè)未訪問過的頂點(diǎn)出發(fā)進(jìn)行遍歷，就可以遍歷完所有的頂點(diǎn)，并且可以得到非連通圖的連通分量個(gè)數(shù)。/從頂點(diǎn)從頂點(diǎn)n出發(fā)，出發(fā)，DFS遍歷遍歷int DFS( int n ) visitedn=1; for(int i=1; i=nodes; i+) if( nodeni=1 &

2、; !visitedi ) DFS(i); return 0;/依次從每個(gè)未訪問過的頂點(diǎn)依次從每個(gè)未訪問過的頂點(diǎn)/出發(fā)出發(fā)DFSsubnets=0;for( int n=1; n=nodes; n+ ) if(!visitedn) DFS(n); subnets+; 3關(guān)節(jié)點(diǎn)及重連通圖0123456789 關(guān)節(jié)點(diǎn)：在一個(gè)無向連通圖關(guān)節(jié)點(diǎn)：在一個(gè)無向連通圖G中，當(dāng)且僅當(dāng)刪去中，當(dāng)且僅當(dāng)刪去G中的頂中的頂點(diǎn)點(diǎn)v及其所關(guān)聯(lián)的邊后，可將圖分割成及其所關(guān)聯(lián)的邊后，可將圖分割成2個(gè)或個(gè)或2個(gè)以上的個(gè)以上的連通分量，則稱頂點(diǎn)連通分量，則稱頂點(diǎn)v為關(guān)節(jié)點(diǎn)為關(guān)節(jié)點(diǎn)(Articulation Point)，或，或

3、者稱為割頂。者稱為割頂。圖圖(1)中，頂中，頂點(diǎn)點(diǎn)1、3、5、7都是關(guān)節(jié)點(diǎn)都是關(guān)節(jié)點(diǎn) 重連通圖：沒有關(guān)節(jié)點(diǎn)的連通圖。在重連通圖上，任何重連通圖：沒有關(guān)節(jié)點(diǎn)的連通圖。在重連通圖上，任何一對頂點(diǎn)之間至少存在有一對頂點(diǎn)之間至少存在有2條路徑，在刪去某個(gè)頂點(diǎn)及其條路徑，在刪去某個(gè)頂點(diǎn)及其所關(guān)聯(lián)的邊時(shí)，也不破壞圖的連通性。所關(guān)聯(lián)的邊時(shí)，也不破壞圖的連通性。4重連通分量 如果連通圖如果連通圖G不是重連通圖，那么它可以包括幾個(gè)重連不是重連通圖，那么它可以包括幾個(gè)重連通分量。一個(gè)連通圖的重連通分量是該圖的極大連通子通分量。一個(gè)連通圖的重連通分量是該圖的極大連通子圖。圖。 圖圖(1)包含了包含了6個(gè)連通分量個(gè)連

4、通分量01234567891775判斷關(guān)節(jié)點(diǎn)的樸素方法依次去掉每個(gè)頂點(diǎn)（及其所關(guān)聯(lián)的邊），然后用依次去掉每個(gè)頂點(diǎn)（及其所關(guān)聯(lián)的邊），然后用DFS去搜索整個(gè)圖，去搜索整個(gè)圖，可得到該圖的連通分量的個(gè)數(shù)，如果是大于可得到該圖的連通分量的個(gè)數(shù)，如果是大于2，則該頂點(diǎn)是關(guān)節(jié)點(diǎn)。，則該頂點(diǎn)是關(guān)節(jié)點(diǎn)。(這種方法復(fù)雜度很高，只適合規(guī)模較小的題目這種方法復(fù)雜度很高，只適合規(guī)模較小的題目)例子：例子：ZOJ 1311/依次去掉每個(gè)頂點(diǎn)依次去掉每個(gè)頂點(diǎn)(及其所關(guān)聯(lián)的邊及其所關(guān)聯(lián)的邊)，用，用DFS遍歷剩下的子圖，得連通分量個(gè)數(shù)遍歷剩下的子圖，得連通分量個(gè)數(shù)for(int m=1; m=nodes; m+)int

5、subnets=0; /子網(wǎng)數(shù)目子網(wǎng)數(shù)目memset(visited,0,sizeof(visited);for( int n=1; n1) SPF+;6/去掉第去掉第m個(gè)頂點(diǎn)及其所關(guān)聯(lián)的邊，從第個(gè)頂點(diǎn)及其所關(guān)聯(lián)的邊，從第n個(gè)頂點(diǎn)出發(fā)進(jìn)行個(gè)頂點(diǎn)出發(fā)進(jìn)行DFSint DFS( int m, int n )visitedn=1;for(int i=1; i=nodes; i+)if( i=m ) continue; /不考慮第不考慮第m個(gè)頂點(diǎn)個(gè)頂點(diǎn)if( nodeni=1 & !visitedi )DFS(m,i);return 0;7 從頂點(diǎn)從頂點(diǎn)3出發(fā)進(jìn)行深度優(yōu)先搜索，得到圖出發(fā)進(jìn)行深

6、度優(yōu)先搜索，得到圖(b)所示的生成所示的生成樹，并改畫成圖樹，并改畫成圖(c)所示的樹形形狀。所示的樹形形狀。 圖圖(c)中每個(gè)頂點(diǎn)外側(cè)的數(shù)字標(biāo)明了進(jìn)行深度優(yōu)先搜索時(shí)中每個(gè)頂點(diǎn)外側(cè)的數(shù)字標(biāo)明了進(jìn)行深度優(yōu)先搜索時(shí)各頂點(diǎn)訪問的次序，稱為頂點(diǎn)的各頂點(diǎn)訪問的次序，稱為頂點(diǎn)的深度優(yōu)先數(shù)深度優(yōu)先數(shù)，可以記在，可以記在數(shù)組數(shù)組dfn中。中。0123456789(a)0123456789(b)1234510987601234(c)1234510987697658求關(guān)節(jié)點(diǎn)的算法8注意：如果u和v是2個(gè)頂點(diǎn)，且在深度優(yōu)先搜索生成樹中u是v的祖先，則有dfnu=dfnu01234(c)1234510987697658哪些頂點(diǎn)是關(guān)節(jié)點(diǎn)？14問題：找到關(guān)節(jié)點(diǎn)以后，去掉該關(guān)節(jié)點(diǎn)，將原來的連通