【文章內(nèi)容簡介】 t(w)。 EnQueue(Q, w)。 // 訪問的頂點(diǎn) w入隊(duì)列 } // if } // while } //if } // BFSTraverse 例如 ， 對圖 813所示無向圖 G7， 從頂點(diǎn) 1出發(fā)的廣度優(yōu)先搜索遍歷序列可有多種 ， 下面僅給出三種 ， 其它可作類似分析 。 在無向圖 G7中 ， 從頂點(diǎn) 1出發(fā)的廣度優(yōu)先搜索遍歷序列舉三種為： 1, 2, 3, 4, 5, 6, 7, 8 1, 3, 2, 7, 6, 5, 4, 8 1, 2, 3, 5, 4, 7, 6, 8 3 1 2 4 5 7 6 8 8 13 無向圖 G 7 用鄰接矩陣實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷 若從頂點(diǎn) 1 出發(fā) ， 廣度優(yōu)先搜索序列為： 1， 2， 3， 4，5， 6， 7， 8。 若從頂點(diǎn) 3出發(fā) ， 廣度優(yōu)先搜索序列為：3， 1， 6， 7， 2， 8， 4， 5,從其它點(diǎn)出發(fā)的廣度優(yōu)先搜索序列可根據(jù)同樣類似方法分析 。 3 1 2 4 5 7 6 8 8 13 無向圖 G 7 0111100010000100100001001000001010000010011000010001100100000110 圖 8 14 無向圖 G 7 的鄰接矩陣 用鄰接表實(shí)現(xiàn)圖的廣序優(yōu)先搜索遍歷 若從頂點(diǎn) 1出發(fā) ， 廣度優(yōu)先搜索序列為： 1， 2， 3， 4，5， 6， 7， 8， 若從頂點(diǎn) 7出發(fā) ， 廣度優(yōu)先搜索序列為： 7， 3， 8， 1， 6， 4， 5， 2， 從其它頂點(diǎn)出發(fā)的廣度優(yōu)先搜索序列可根據(jù)同樣類似方法分析 。 3 1 2 4 5 7 6 8 8 13 無向圖 G 7 1 2 3 4 5 6 7 8 2 3 ^ 1 4 1 6 2 8 ^ 2 8 ^ 3 8 ^ 3 8 ^ 4 5 6 7 ^ 7 ^ 5 ^ 圖 8 16 G 7 的鄰接表 廣度優(yōu)先搜索算法分析 分析前述過程，每個頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過程實(shí)質(zhì)上是通過邊或弧找鄰接 點(diǎn)的過程、因此廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之 處僅僅在于對頂點(diǎn)訪問的順序不同。 圖遍歷的應(yīng)用 假設(shè)圖 G采用鄰接表存儲，設(shè)計(jì)一個算法，判斷無向圖 G是否連通。若連通則返回 1；否則返回 0。 int Connect(ALGraph *G) /*判斷無向圖 G的連通性 */ { int i,flag=1。 for (i=0。iGn。i++) /*visited數(shù)組置初值 */ visited[i]=0。 DFS(G,0)。/*調(diào)用 DSF算法 ,從頂點(diǎn) 0開始深度優(yōu)先遍歷 */ for (i=0。iGn。i++) if (visited[i]==0) { flag=0。 break。 } return flag。 } 假設(shè)圖 G采用鄰接表存儲，設(shè)計(jì)一個算法，輸出圖 G中從頂點(diǎn) u到 v的長度為 l的所有簡單路徑。 分析：所謂簡單路徑是指路徑上的頂點(diǎn)不重復(fù)。 利用回溯的深度優(yōu)先搜索方法。 從頂點(diǎn) u開始，進(jìn)行深度優(yōu)先搜索，在搜索過程中，需要把當(dāng)前的搜索線路記錄下來。為此設(shè)立一個數(shù)組 path保存走過的路徑，用 d記錄走過的路徑長度。若當(dāng)前掃描到的結(jié)點(diǎn) u等于 v且路徑長度為 l時，表示找到了一條路徑，則輸出路徑 path。 對應(yīng)的算法如下： void PathAll(ALGraph *G,int u,int v,int l,int path[],int d) /*d是到當(dāng)前為止已走過的路徑長度，調(diào)用時初值為 1*/ { int m,i。 ArcNode *p。 visited[u]=1。 d++。 /*路徑長度增 1*/ path[d]=u。 /*將當(dāng)前頂點(diǎn)添加到路徑中 */ if (u==v amp。amp。 d==l) /*輸出一條路徑 */ { printf( )。 for (i=0。i=d。i++) printf(%d ,path[i])。 printf(\n)。 } p=Gadjlist[u].firstarc。 /*p指向 u的第一條弧的弧頭結(jié)點(diǎn) */ while (p!=NULL) { m=padjvex。 /*m為 u的鄰接頂點(diǎn) */ if (visited[m]==0) /*若頂點(diǎn)未標(biāo)記訪問 ,則遞歸訪問之 */ PathAll(G,m,v,l,path,d)。 p=pnextarc /*找 u的下一個鄰接頂點(diǎn) */ } visited[u]=0。 /*恢復(fù)環(huán)境 */ } 圖的連通性問題 一 、 無向圖的連通分量和生成樹 若圖是 連通 的或 強(qiáng)連通 的，則從圖中 某一個頂點(diǎn)出發(fā)可以訪問到圖中 所有頂點(diǎn) ； 若圖 是非連通 的或 非強(qiáng)連通 圖，則需從圖中多個頂點(diǎn) 出發(fā)搜索訪問而每一次從一個新的起始點(diǎn)出發(fā)進(jìn)行搜索，搜索過程中得到的頂點(diǎn)訪問序列恰為每個 連通分量 中的 頂點(diǎn)集 。 D E A B C F J L M G H I K D E G H I K A B C F J L M 對于 連通圖 ， 深度優(yōu)先搜索遍歷算法及廣度優(yōu)先搜索遍歷算法中遍歷圖過程中歷經(jīng)邊的集合和頂點(diǎn)集合一起構(gòu)成 連通圖 的 極小連通子圖 。 它是連通圖的一棵 生成樹 。 生成樹： 是一個極小連通子圖 ， 它含有圖中全部頂點(diǎn) ， 但只有 n1條邊 。 由深度優(yōu)先搜索遍歷得到的生成樹 ， 稱為深度優(yōu)先生成樹 ， 由廣度優(yōu)先搜索遍歷得到的生成樹 ， 稱為 廣度優(yōu)先生成樹 。 連通圖的生成樹 1 4 2 5 3 6 8 7 2 7 6 8 3 5 4 1 (a ) 深度優(yōu)先生成樹 (b) 廣度優(yōu)先生成樹 圖 8 1 9 兩種生成樹示意圖 3 1 2 4 5 7 6 8 8 13 無向圖 G 7 例 1 ：畫出下圖的生成樹 DFS生成樹 v0 v1 v2 v4 v4 v3鄰接表 0 1 2 3 4 ^ 1 3 3 4 ^ 1 4 2 ^ 0 v4 v3 v2 v1 v0 2 3 ^ 1 4 2 ^ 0 v0 v2 v1 v4 v3 BFS生成樹 v0 v1 v3 v2 v4 無向連通圖 2．生成森林 若一個圖 是非連通圖 或 非強(qiáng)連通圖 ， 但有若干個 連通分量 或若干個 強(qiáng)連通分量 ， 則通過 深度優(yōu)先 搜索遍歷或 廣度優(yōu)先 搜索遍歷 ， 不可以 得到生成樹 ， 但 可以 得到 生成森林 ， 且若非連通圖有 n 個頂點(diǎn) ， m 個連通分量或強(qiáng)連通分量 ， 則可以遍歷得到 m棵生成樹 ， 合起來為生成森林 ， 森林中包含 nm條樹 邊 。 生成森林可以利用非連通圖的 深度優(yōu)先搜索遍歷 或非連通圖的 廣度優(yōu)先搜索遍歷算法 得到 。 3． 最小生成樹 在一般情況下 ， 圖中的每條邊若給定了 權(quán) ， 這時 ， 我們所關(guān)心的不是生成樹 ， 而是 生成樹中邊上權(quán)值之和 。 若 生成樹中每條邊上權(quán)值之和達(dá)到最小 ， 稱為 最小生成樹 。 構(gòu)造最小生成樹的準(zhǔn)則 ?必須只使用該網(wǎng)絡(luò)中的 邊 來構(gòu)造最小生成樹； ?必須使用且僅使用 n1條邊 來 聯(lián)結(jié)網(wǎng)絡(luò)中的 n個頂點(diǎn)； ?不能使用產(chǎn)生 回路 的邊。 欲在 n個城市間建立通信網(wǎng)，則 n個城市應(yīng)鋪 n1條線路；但因?yàn)槊織l線路都會有對應(yīng)的經(jīng)濟(jì)成本，而 n個城市可能有 n(n1)/2 條線路，那么， 如何選擇 n–1條線路，使總費(fèi)用最少？ 典型用途： 數(shù)學(xué)模型： 頂點(diǎn) ———表示城市，有 n個； 邊 ————表示線路，有 n–1條； 邊的權(quán)值 —表示線路的經(jīng)濟(jì)代價； 連通網(wǎng) ——表示 n個城市間通信網(wǎng)。 問題抽象： n個頂點(diǎn)的生成樹很多，需要從中選一棵代價最小 的生成樹，即該樹 各邊的代價之和 最小。此樹便稱為最小生成樹 MST(Minimum cost Spanning Tree) 顯然此連通網(wǎng)是一個 生成樹！ 求最小生成樹的兩種方法 普里姆算法和克魯斯卡爾算法 普里姆 (prim)算法思想 在圖中任取一個 頂點(diǎn) k作為開始點(diǎn)，令 U={k}，W=VU，其中 V為圖中所有頂點(diǎn)集，然后找一個 頂點(diǎn)在 U中 ，另 一個頂點(diǎn)在 W中 的 邊中最短的一條 ，找到后，將該邊作為最小生成樹的樹邊保存起來，并將 該邊頂點(diǎn)全部加入 U集合 中，并從 W中刪去這些頂點(diǎn) ，然后重新調(diào)整 U中頂點(diǎn)到 W中頂點(diǎn)的距離 , 使之保持 最小 ，再 重復(fù)此過程 ，直到 W為空 集止。 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 3 1 1 6 3 1 4 1 6 4 3 1 4 2 1 1 6 4 3 2 1 4 2 5 1 6 5 4 3 2 1 4 2 5 3 Prim算法構(gòu)造最小生成樹過程 a b c d e g f 例如 :利用 普里姆 算法構(gòu)造最小生成樹 19 5 14 18 27 16 8 21 3 12 7 所得生成樹權(quán)值和 = 14+8+3+5+16+21 = 67 假設(shè)開始頂點(diǎn)就選為頂點(diǎn) 1， 故首先有 U={1}， W={2，3， 4， 5， 6}