算法設(shè)計(jì)與分析

1、算法設(shè)計(jì)與分析第六小組講稿小組成員： 任務(wù)分工：1、基本概念2、生成樹算法3、最?。ù螅┖馁M(fèi)生成樹算法4、最大分枝算法）一、基本概念毛科技1. 一個(gè)無向圖G是一個(gè)有序的二元組（V，E）表示： V稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)。E稱為邊集，它是無序積V&V的多重子集，其元素稱為無向邊，簡(jiǎn)稱邊。 一個(gè)有向圖是一個(gè)有序的二元組（V，E），記作D， 其中：V同無向圖 E為邊集，它是笛卡兒積V*V的多重子集，其元素稱為有向邊，簡(jiǎn)稱邊。（多重集合：元素可以重復(fù)出現(xiàn)的集合）V: ,E: a, b, c, d, e例如：cde a ba2. 網(wǎng)絡(luò)：圖中的每條邊附有一個(gè)或幾個(gè)數(shù)字。a b 1 2 1 2cbc

2、 3 網(wǎng)絡(luò) 非網(wǎng)絡(luò)3. 自環(huán)：有向邊（?。┑念^部和尾部為同一個(gè)頂點(diǎn)。ba 自環(huán) 非自環(huán)4. 某個(gè)頂點(diǎn)為某一條弧的一個(gè)端點(diǎn)（頭或尾），則此頂點(diǎn)與該條弧相關(guān)聯(lián)。5. 如果兩條弧都和同一個(gè)頂點(diǎn)關(guān)聯(lián)，則該兩條弧稱為相互關(guān)聯(lián)。如有一條弧將兩個(gè)頂點(diǎn)連接起來，則這兩個(gè)頂點(diǎn)稱為鄰接。ab e1 e2 e3 在上圖中e1和a，e1和e2為相互關(guān)聯(lián)，a和b 為鄰接6. 鏈：給定任一頂點(diǎn)序列X1，X2，X3，Xn,Xn+1,若弧e1的兩個(gè)端點(diǎn)是Xi和Xi+1，i=1，n 。則稱弧的序列e1，e2，en 為鏈。頂點(diǎn)X1，Xn+1分別稱為鏈的始點(diǎn)和終點(diǎn)。鏈中弧的數(shù)目稱為鏈的長(zhǎng)度。鏈：X4X3X1X2 e1 e2 e3

3、e4 在鏈中的頂點(diǎn)不可以重復(fù)，但是對(duì)弧的序列沒有要求。如果一個(gè)鏈的始點(diǎn)和終點(diǎn)為 同一點(diǎn)，這樣的鏈稱為圈。在鏈和圈中如果不存在和兩條以上的弧相關(guān)聯(lián)的頂點(diǎn)時(shí)，分別稱為簡(jiǎn)單鏈和簡(jiǎn)單圈。X3X2X1 簡(jiǎn)單圈7. 路：若ei=（Xi，Xi+1），i=1，n ，這樣的鏈稱為路。如果一條鏈的始點(diǎn)和終點(diǎn)為同一點(diǎn)，這樣的鏈稱為圈。如果一條路的始點(diǎn)和終點(diǎn)為同一點(diǎn)，這樣的路稱為回路。圈或回路的長(zhǎng)度定義為這條相應(yīng)的鏈的長(zhǎng)度。路：X3X2X2X1 e1 e2 e3 e4 在路中的弧的序列不可以重復(fù)。但是對(duì)頂點(diǎn)沒有要求。 簡(jiǎn)單回路：除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的路。 簡(jiǎn)單路：在路中如果不存在和兩條

4、以上的弧相關(guān)聯(lián)的頂點(diǎn)。8. 連通圖：在一個(gè)圖內(nèi)，如果每一對(duì)頂點(diǎn)都有一條鏈將它們連接起來。一個(gè)圖可以看成是有連通圖的一個(gè)集合組成，其中每一個(gè)連通圖稱為原圖的一個(gè)分圖。edcba非連通圖edcba9. 給定圖G=（V，E），如果V V，E E，則圖G=（V，E）稱為G的子圖。從圖中刪去弧的一個(gè)子集時(shí)，若能增加圖中分圖的數(shù)目，則稱刪去的弧的集合為圖的截。fda e1bec 圖中只有e1是截10. 滿足下列條件的弧的集合稱為樹：（1） 這些弧構(gòu)成一個(gè)連通圖。（2） 這些弧不構(gòu)成圈。 樹的定義：是N（N0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：1，有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)。2，當(dāng)N1時(shí)，其余結(jié)點(diǎn)可分

5、為M（M0）個(gè)互不相交的有限集T1，T2，T3，Tm，其中每一個(gè)集合本身又是一棵樹。aacbcbdeed 樹 圈11. 森林：不包含圈的任一弧的集合。其包含一棵或多棵樹。給定圖G=（V，E），G=(V，E)是G的連通子圖，E E，E有且僅有N-1條邊（G有N個(gè)頂點(diǎn)），則稱G是G的一棵生成樹。每一個(gè)連通圖都有一棵生成樹；有兩個(gè)或兩個(gè)以上分圖的圖不存在生成樹；一個(gè)連通圖的生成樹不一定是唯一的。設(shè)T是無向圖G的子圖并且為樹，則稱T為G的樹。若T是G的樹且為生成子圖，則稱T是G的生成樹。12. 最小耗費(fèi)生成樹：設(shè)G是一個(gè)有頂點(diǎn)的無向圖，圖中的每一條邊eiE都有一個(gè)權(quán)Ci， Ci稱為ei的耗費(fèi)。生成樹的

6、各邊的耗費(fèi)之和稱為生成樹的耗費(fèi)。在圖G的一切生成樹中，各邊耗費(fèi)之和最小的一棵生成樹稱為G的最小耗費(fèi)生成樹。圖G的最小耗費(fèi)生成樹不一定是唯一的。13. 用矩陣來表示圖：設(shè)G是N個(gè)頂點(diǎn)M條弧的任一無自環(huán)的圖，H為一矩陣，它有N行（每個(gè)頂點(diǎn)對(duì)應(yīng)于一行）和M列（每條弧對(duì)應(yīng)于一列）。Hij表示第i行和第j列的元素，Hij的定義如下： +1 如果第i行的頂點(diǎn)是第j列的弧的頭部 Hij= -1 如果第i行的頂點(diǎn)是第j列的弧的尾部 0 不屬于以上兩種情況H的每一列只含+1各一個(gè)，其余元素均為0。 e1 e2 e3 e4 e5 a -1 -1 +1 0 0 H= b +1 +1 0 -1 -1 c 0 0 -1

7、 +1 +1 d 0 0 0 +1 -1耗費(fèi)矩陣： 1 2 3 4 512751443241274135323 1 2 3 4 5對(duì)于無向圖，可以用鄰接矩陣來表示。矩陣中只有0，1兩個(gè)元素 H= 1 頂點(diǎn)I與頂點(diǎn)j間有邊相鄰 0 否則 a b c d e a 0 1 1 0 0 b 1 0 1 1 1 H= c 1 1 0 1 0 d 0 1 1 0 1 e 0 1 0 1 0edbca二、生成樹算法 龐若蔚剛才毛科技同學(xué)介紹了圖的一些相關(guān)基本概念，下面我們來探討一下圖的生成樹。前面講到，對(duì)于給定的圖G=(V,E),G=(V,E)是G的連通子圖，EE,E有且僅有n-1條邊（G有n個(gè)頂點(diǎn)），則稱

8、G是G的一棵生成樹，每一棵連通圖都有一棵生成樹，有兩個(gè)獲兩個(gè)以上分圖的圖不存在生成樹，但一個(gè)連通圖的生成樹不是唯一的，對(duì)于一個(gè)給定的圖，常常含有許多不同的樹。我介紹的是生成樹的算法。在實(shí)際應(yīng)用中，解決離散對(duì)象的問題時(shí)，由于數(shù)目有限，常可以采用窮舉法，生成樹的算法就是窮舉法。具體步驟如下：S1. 所有的邊都未著色，所有的桶為空。S2. 任意選一條非自環(huán)的邊，對(duì)此邊著紅色，（著紅色邊表示這條邊是生成樹內(nèi)的邊），并把此邊的兩個(gè)端點(diǎn)放入同一個(gè)桶內(nèi)。S3. 再任意另選一條還沒有著色的非自環(huán)的邊，有以下幾種情況：（1）若沒有這樣的邊，著算法終止，此時(shí)無生成樹（2）這條邊的兩個(gè)端點(diǎn)在同一個(gè)桶內(nèi)，則對(duì)此邊著藍(lán)

9、色（表示不在生成樹內(nèi)），回到S3（3）這條邊的一個(gè)端點(diǎn)在桶內(nèi)，另一個(gè)端點(diǎn)不在任何桶內(nèi)，此時(shí)將這條邊著紅色（在樹內(nèi)），并把不在桶內(nèi)的端點(diǎn)放入另一端點(diǎn)所在的桶內(nèi)，轉(zhuǎn)到S4（4）這條邊的兩個(gè)端點(diǎn)都不在任何桶內(nèi)，此時(shí)將這條邊著紅色，并將兩個(gè)端點(diǎn)放入同一空桶，轉(zhuǎn)到S4（5）兩個(gè)端點(diǎn)分別在不同的桶內(nèi)。此時(shí)將這條邊著紅色，并把兩個(gè)桶內(nèi)的端點(diǎn)并入一個(gè)桶，是另一桶為空桶。轉(zhuǎn)到S4S4. 判斷G的所有定點(diǎn)是否都在一個(gè)桶內(nèi)。若是，則所有紅邊構(gòu)成生成樹，算法結(jié)束；否則轉(zhuǎn)到S3這個(gè)算法每循環(huán)一次必有一條邊被著色，且每條邊最多只檢驗(yàn)一次。假設(shè)檢查每一條邊耗費(fèi)單位時(shí)間（包括選邊，檢查，著色），那么該算法的最壞情況的時(shí)間復(fù)雜

10、性為O(IIEII).講課時(shí)會(huì)附以盧開澄教材中的圖2.3.1三、最?。ù螅┖馁M(fèi)生成樹算法 鄭月鋒1、最小耗費(fèi)生成樹對(duì)于連通的帶權(quán)圖(連通網(wǎng))G，其生成樹也是帶權(quán)的。生成樹T各邊的權(quán)值總和稱為該樹的權(quán)，記作： 這里: TE表示T的邊集 w(u，v)表示邊(u，v)的權(quán)。 權(quán)最小的生成樹稱為G的最小耗費(fèi)生成樹(Minimum Spannirng Tree)。最小生成樹可簡(jiǎn)記為MST。2、最小耗費(fèi)生成樹的應(yīng)用生成樹和最小生成樹有許多重要的應(yīng)用。如：網(wǎng)絡(luò)G表示n各城市之間的通信線路網(wǎng)線路（其中頂點(diǎn)表示城市，邊表示兩個(gè)城市之間的通信線路，邊上的權(quán)值表示線路的長(zhǎng)度或造價(jià)?？赏ㄟ^求該網(wǎng)絡(luò)的最小生成樹達(dá)到求解

11、通信線路或總代價(jià)最小的最佳方案。3、 最小耗費(fèi)生成樹的算法3.1 Kruskal算法3.1.1 Kruskal算法的基本思想：首先將圖G的邊按權(quán)的遞增順序進(jìn)行排列，不失一般性設(shè)為：e1, e2, e3, em ，其中wkwk+1。然后在不構(gòu)成回路的條件下，擇優(yōu)取進(jìn)權(quán)最小的邊。3.1.2 Kruskal算法介紹Kruskal算法過程（見教材P143）B e6=2 E3.1.3 Kruskal算法在求解最小耗費(fèi)生成樹中的應(yīng)用e15 = 1 e13 =5 e7 = 3 e1 = 7 e4 = 1 e8 = 2 e9 = 7 e2 = 8 FACHe16= 3 e14 = 4 e10 = 3 e11

12、= 4e5 = 4 e17 = 6 e3 = 2 e12 = 6 GD如上圖中，對(duì)各邊按權(quán)的大小遞增順序進(jìn)行排列：e 4 （1）= 1 ， e 15 （2）= 1 ， e 3 （3）= 2 ，e 6 （4）= 2 ，e 8 （5）= 2 ，e 7 （6）= 3 ，e 10（7）= 3 ， e 16（8）= 3 ， e 5 （9）= 4 ，e 11 （10）= 4，e 14 （11）= 4，e 13 （12）= 5，e 12（13）= 6， e 17 （14）= 6， e 1 （15）= 7，e 9 （16）= 7 ，e 2 （17）= 8右上肩括號(hào)里的數(shù)是排序的序號(hào)。按Kruskal算法得到的

13、最小耗費(fèi)樹為：（4）EB（2）（1）FC（7）（8）HA（9）（3）GD其中，T中每條邊括號(hào)里的數(shù)為進(jìn)入T的序號(hào)，T的權(quán)為16。3.1.4 Kruskal算法復(fù)雜性分析時(shí)間復(fù)雜性為O（mlog2m）。3.2 Prim算法3.2.1 Prim算法的基本思想：從某一頂點(diǎn)（設(shè)為V1）開始，令SV1，求V-S中點(diǎn)與S中點(diǎn)V1權(quán)最小的點(diǎn)，令SSV1，繼續(xù)求V-S中點(diǎn)與S中點(diǎn)V1權(quán)最小的點(diǎn)，設(shè)為Vk , 令SSVk,繼續(xù)以上的步驟，直到n個(gè)頂點(diǎn)用n-1條邊連接起來為止。3.2.2 Prim算法介紹Prim算法過程：(1) 初始化操作：T，q(1) -1,i從2到n作p(i) 1, q(i) di1,k1。

14、(2) 若kn，則作輸出T，結(jié)束。否則，作min；j從2到n作若0q(i)min 則作minq(i),hj(3) TT(h,p(h),q(h) -1。(4) j從2到n作若dhj =0，a（t，s）=a（r，s），又因?。╰，y）被選為指向頂點(diǎn)y的弧，所以a（t，y）=a（x，y）。 令Vi+1包含Gi+1中在vi內(nèi)的所有各頂點(diǎn)（于是，viVi+1）。Ai+1包含Gi+1中在Ai內(nèi)的所有各條弧 i i+1，轉(zhuǎn)第一步第三步：僅當(dāng)Gi中所有各個(gè)頂點(diǎn)都在Vi中，且Ai內(nèi)的弧構(gòu)成Gi的一個(gè)分枝時(shí)，才執(zhí)行這一步。如i=0，則停止，此時(shí)A0內(nèi)的弧構(gòu)成G0的一個(gè)最大分枝。 如i！=0，則有下面兩種可能：1 頂點(diǎn)Vi-1是Ai中某個(gè)樹形圖的根。2 頂點(diǎn)Vi-1不是Ai中某個(gè)樹形圖的根。如果1 發(fā)生了，則考慮Ai中的弧連同回路Ci-1中的各條弧。這些弧包含圖Gi-1中的一個(gè)回路，即Ci-1。從弧集合中刪去Ci-1中有最小權(quán)的一條弧。這樣得到的弧集合構(gòu)成Gi-1的一個(gè)分枝。重新定義Ai-1為這個(gè)弧集合。如果2 發(fā)生，則Ai中有唯一的一條指向頂點(diǎn)Vi-1的?。▁，vi-1）?；。▁， vi-1）對(duì)應(yīng)圖Gi-1中的另一條弧，設(shè)為（x,y）,其頂點(diǎn)y是回路Ci-1的一