【文章內(nèi)容簡介】 )。 ?對輔助數(shù)組初始化時間為 O(n)。 ?因此，當(dāng)用鄰接表作為圖的存儲結(jié)構(gòu)時，廣度優(yōu)先搜索圖的時間復(fù)雜性為 O(e+n)。 返回 最小生成樹 ?在一個無向連通圖 G中，如果取它的全部頂點和一部分邊構(gòu)成一個子圖 G’，若邊集 E(G’)中的邊剛好將圖的所有頂點連通但又不形成環(huán)路，我們就稱子圖 G’是原圖 G的生成樹（ Spanning tree）。 ?生成樹有如下特點：任意兩個頂點之間有且僅有一條路徑；如果再增加一條邊就會出現(xiàn)回路；如果去掉一條邊此子圖就會變成非連通圖。 ?一個有 n 個頂點的完全圖，一共存在 n(n2)種不同的生成樹。 ?對于帶權(quán)的連通圖（連通網(wǎng)） G，其生成樹也是帶權(quán)的。我們把生成樹各邊的權(quán)值總和稱為該生成樹的權(quán)。并且將權(quán)最小的生成樹稱為最小生成樹（ Minimum Spanning Tree）。 ?具有 n個頂點的連通圖的生成樹具有 n1條邊（少于此邊數(shù)不可能將各頂點連通，多于此邊數(shù)則必然要出現(xiàn)回路） 。 圖 圖 G 及其生成樹 ?無向連通圖 G ⑤ ④ ① ② ③ 0 6 5 6 6 5 5 1 3 4 2 ⑤ ④ ① ② ③ 0 6 6 5 5 4 ?生成樹 圖 圖 G 及其生成樹 ?生成樹 ⑤ ④ ① ② ③ 0 6 1 3 4 2 ⑤ ④ ① ② ③ 0 5 1 3 4 2 ?最小生成樹 (prim)算法 ?基本思想： 假設(shè) N=（ V， E）是連通的， TE是N上最小生成樹中的邊集。 首先從某一結(jié)點 U。開始， 令 U={U。 }， TE=?， 重復(fù)下列工作：從一個頂點在 U中，另一個頂點在 VU中，找權(quán)值最小的邊 U。， V。 , 并加入集合 TE中，同時， V。加入 U 中。 直到 U=V為止。此時，有 n1條邊， T=（ V， TE）為 N的最小生成樹。 假設(shè) G=(V, E)是一個具有 n 個頂點的連通網(wǎng)絡(luò)， T=(U,TE)是 G的最小生成樹，其中 U是 T的頂點集， TE是 T的邊集， U和 TE的初值均為空。 算法開始時，首先從 V中任取一個頂點（假定為 V。），將此頂點并入 U中，此時最小生成樹頂點集 U={V。 }； 然后 ,從那些其一個端點已在 U中，另一個端點在 VU中，找一條最短（即權(quán)值最小）的邊，假定該邊為 (Vi, Vj), 其中 Vi∈ U， Vj∈ VU, 并把該邊 (Vi, Vj)和頂點 Vi分別并入 T的邊集 TE和頂點 集 U中 . 如此進(jìn)行下去，每次往生成樹里并入一個頂點和一條邊，直到 n1次后，把所有 n 個頂點都并入生成樹 T的頂點集 U中，此時 U=V， TE中包含有（ n1）條邊； 這樣， T就是最后得到的最小生成樹。 ?普里姆算法中每次選取的邊兩端，總是一個在 U 中，一個在 VU 中，故這個邊選取后一定能將未連通頂點連通而又保證不會形成環(huán)路。 圖 普里姆算法例子 8 3 5 ⑤ ④ ① ② ③ 9 14 17 13 12 18 ????????????????????????5181251317141813391738121498C?為了便于在頂點集合 U和 VU之間選擇權(quán)最小的邊，需建立一個數(shù)組 closedge[v], (v∈V U),記錄從 U到 VU之間權(quán)最小的邊 . closedge[v]有兩個字段 : closedge[v].vex: 存放與該邊相關(guān)聯(lián)的在 U中的頂點 , closedge[v].lowcost: 存放該邊的權(quán) . 普里姆算法 : void prim( gn, 1) /*gn: 圖的鄰接矩陣 ， 頂點為 { /* {1,2,… ,n}, 從頂點 1開始 for( i=2, i=n。 i++) /*從頂點 2開始初始化 */ { closedge[i].vex=1。 closedge[i].lowcost=gn[1, i]。 } closedge[1].lowcost=0。 /*頂點 1加入 U中 . For( i=1。 i,=n1。 i++) /*求 n1條邊 { j=min(closedge)。 /* j∈V U printf(“… ”, closedge [j]. vex, j)。 /*輸出一條邊 closedge [j]. lowcost=0。 /*頂點 j加入 U中 . for (k=1。 k=n。 k++) if (gn [j, k] closedge [k]. lowcost。 { closedge[k].lowcost=gn[j, k]。 closedge[k].vex= j 。 } } } 算法分析 ?該算法中每一步執(zhí)行都要掃描數(shù)組 lowcost，在 VU頂點集中找出與 U最近的頂點，令其為 k，并打印邊（ k,closest[k]）。 ?然后將 k加入 U頂點集合中，并修改數(shù)組lowcost和 closest。 ?這里用 c表示圖的鄰接矩陣， c[i][j]和 c[j][i]是邊 (i,j)的權(quán)。 2 克魯斯卡爾（ Kruskal）算法 ?基本思想：設(shè) G=（ V， E），最小生成樹的初態(tài)只有 n個結(jié)點，無邊，即 T=（ V， ?）， 從圖 G中選擇一條權(quán)值最小的邊，若此邊加入 T后， T中不產(chǎn)生回路，則把該邊加入 T，否則放棄；選下一條邊 , …… , 直到 T中有 n1條邊為止。 ?現(xiàn)以圖 (a)圖為例說明此算法。 ?設(shè)此圖是用邊集數(shù)組表示的，邊集數(shù)組是一個結(jié)構(gòu)數(shù)組，數(shù)組中的每個元素表示一條邊，組成每條邊的是三元組序列（邊的起始頂點、邊的終止頂點、邊的權(quán)值）。 ?將每條邊的數(shù)據(jù)輸入之后，按權(quán)值的大小進(jìn)行了排序，如圖 (b) 所示。這樣，按權(quán)值由小到大選取各邊就是在數(shù)組中按下標(biāo)由 1到 e(圖中邊的數(shù)目 )的次序選取。 圖 克魯斯卡爾算法例子 ? (a)帶權(quán)圖 ⑥ 8 5 18 ⑤ ④ ① ② ③ 4 23 12 15 25 20 10 ? (b)邊集數(shù)組 1 2 2 3 2 4 1 4 1 5 5 3 4 4 6 6 2 5 6 6 4 5 8 10 12 15 18 20 23 25 1 2 3 4 5 6 7 8 9 10 起點 終點 權(quán)值 ? (c)最小生成樹 8 5 18 ⑥ ⑤ ④ ① ② ③ 4 12 ?在選取某邊時如何判斷是否與已保留的邊形成環(huán)路？克魯斯卡爾算法是通過將各頂點劃分為集合的辦法來解決的。 ?開始時假定 n 個頂點分屬于 n 個集合，即每個集合中有一個頂點，當(dāng)確定某條邊作為生成樹的一條邊時，就將該邊兩端點所屬的兩集合合并為一個，表示原來屬于兩個集合的各個頂點已被這條新的邊連通。如果取到某條邊，發(fā)現(xiàn)它的兩個端點已屬于同一集合時，此邊則應(yīng)當(dāng)舍去。因為兩個頂點屬于同一集合說明它們已連通，若再添上這條邊就會出現(xiàn)環(huán)路。 ?如此進(jìn)行下去，到所有的頂點均已屬于一個集合時，此最小生成樹就構(gòu)成了。 ?用一個 set[ ]數(shù)組來表示頂點， set的初值為s[i]=0(i=1,2,…,n), 表示各頂點自成一個分量。當(dāng)從邊集數(shù)組中按次序選取一條邊時，查找它的兩個頂點所屬的分量，當(dāng)這兩個分量不相等，則表明所選的這條邊的兩個頂點分屬不同的集合，該邊加入到生成樹中不會形成環(huán)路，應(yīng)作為生成樹的一條邊，同時合并這兩個分量為一個連通分量。若這兩個分量相等，則表明這條邊的兩個頂點同屬一個集合，將此邊加入到生成樹必產(chǎn)生環(huán)路，應(yīng)予放棄。 ?利用克魯斯卡爾構(gòu)造最小生成樹的邊集數(shù)組結(jié)構(gòu)定義如下： define MAXE 100 struct edges /* 邊集類型 ， 存儲一邊條的起始頂點為 bv,終止頂點為 tv和權(quán) w */ { int bv,tv,w。 } typedef struct edges edgeset[MAXE]。 查找一個頂點所屬的分量函數(shù)如下： int seeks(int set[],int v) { int i=v。 while(set[i]0) i=set[i]。 return(i)。 } 克魯斯卡爾算法 void kruskal (edgeset ge, int n, int e) /* ge為權(quán)按從小到大排序的邊集數(shù)組 */ { int set[MAXE], v1, v2, i, j。 for (i=1。i=n。i++) set[i]=0。 /*給 set中每個元素賦初值 */ i=1。 /* i表示獲取的生成樹中的邊數(shù) ， 初值為 1*/ j=1。 /* j表示 ge中的下標(biāo) ， 初始值為 1*/ while (jn amp。amp。 i=e) /* 檢查該邊是否加入到生成樹中