1、信息學院信息技術教研室VsVtV2V4V3V12484279146V1V8V9V10V7V4V3V6V5V2王桂平王桂平第第3 3章章 樹與圖的生成樹樹與圖的生成樹2例1下圖所示的網絡代表6個城市間的交通網，邊上權是公路的造價，現在要用公路把6個城市聯系起來，這要修筑5條公路，如何設計使得這5條公路總的造價最小。1562431619212318141165631 生成樹：連通圖G的一個子圖如果是一棵包含G的所有頂點的樹，則該子圖稱為G的。用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發，也可能得到不同的生成樹。生成樹是連通圖的。所謂是指：；按照生成樹的定義， 個頂點的連通網絡的生成

2、樹有 個頂點、 條邊。4最小生成樹(MST, Minimum Spannirng Tree)：生成樹各邊的權值總和稱為生成樹的權，權最小的生成樹稱為最小生成樹。 構造最小生成樹的準則：1. 必須只使用該網絡中的邊來構造最小生成樹；必須只使用該網絡中的邊來構造最小生成樹；2. 必須使用且僅使用必須使用且僅使用 n-1 條邊來聯結網絡中的條邊來聯結網絡中的 n 個頂個頂點；點；3. 不能使用產生回路的邊。不能使用產生回路的邊。 構造最小生成樹的方法：算法和算法。都得遵守以上準則。52 克魯斯卡爾算法 先看例子。 克魯斯卡爾算法的基本思想()：1. 設有一個有設有一個有 n 個頂點的連通網絡個頂點的

3、連通網絡 N = V, E ，最初，最初先構造一個只有先構造一個只有 n 個頂點，沒有邊的非連通圖個頂點，沒有邊的非連通圖 T = V, , 圖中每個頂點自成一個連通分量。圖中每個頂點自成一個連通分量。2. 當在當在 E 中選到一條具有最小權值的邊時中選到一條具有最小權值的邊時,若該邊的兩若該邊的兩個頂點落在不同的連通分量上個頂點落在不同的連通分量上，則將此邊加入到，則將此邊加入到 T 中；否則將此邊舍去，重新選擇一條權值最小的邊。中；否則將此邊舍去，重新選擇一條權值最小的邊。3. 如此重復下去，直到所有頂點在同一個連通分量上如此重復下去，直到所有頂點在同一個連通分量上為止。為止。670562

4、342811025242218121614056234110252212161402418140251024250221822012120161416028102808在在Kruskal算法里要用到算法里要用到(MinHeap)和和(DisjointSets)。用來存放用來存放E中所有的邊。中所有的邊。用來檢查依附于用來檢查依附于1條邊的條邊的2個頂點是否在同一個個頂點是否在同一個連同分量上。連同分量上。9為簡化起見，本算法中不使用為簡化起見，本算法中不使用和和，分別使用，分別使用和和來替代并查集和最小堆，并且可以很好地來替代并查集和最小堆，并且可以很好地體現算法的思想。體現算法的思想。Ver

5、UnionVerNum：1) 其中的元素值相同的話，表示在其中的元素值相同的話，表示在上，初上，初始時，每個元素的值為其下標，即每個頂點始時，每個元素的值為其下標，即每個頂點。2) 在最小生成樹產生過程中，如果查找到的權值最小的邊在最小生成樹產生過程中，如果查找到的權值最小的邊的兩個頂點在同一個連通分量（元素值相同），則要的兩個頂點在同一個連通分量（元素值相同），則要，如果不在同一個連同分量上，則要把這條邊，如果不在同一個連同分量上，則要把這條邊加進來，并把加進來，并把設為相同。設為相同。10AdjUnionAdjNum4：1) 二維數組中的每個元素的二維數組中的每個元素的4個分量分別為標志個

6、分量分別為標志F、每條邊、每條邊的起點的起點i、終點、終點j、權值、權值w。2) 標志位初始值為標志位初始值為0，表示邊沒有加入到生成樹中，初始，表示邊沒有加入到生成樹中，初始時邊的集合為空集。時邊的集合為空集。3) 標志位的修改，當查找到權值最小的邊，并且這條邊的標志位的修改，當查找到權值最小的邊，并且這條邊的2個頂點不在同一個連通分量上，則修改對應的標志位個頂點不在同一個連通分量上，則修改對應的標志位為為1，如果在同一個連通分量上，則這條邊要舍去，對，如果在同一個連通分量上，則這條邊要舍去，對應的標志位設為應的標志位設為-1。00128Fijw11本算法思想1.先在二維數組AdjUnion

7、里查找到權值最小的邊（標志位為1和-1的不予考慮）2.檢查這條邊的2個頂點i和j是不是在同一個連通分量上（在一維數組VerUnion里通過判斷這條邊的2個頂點為下標的元素值是否相同），如果在同一個連同分量上，則舍去（在AdjUnion將這條邊的標志置為-1），如果不在的話，執行下列操作：1) 輸出這條邊輸出這條邊;2) 將標志位置為將標志位置為1;3) 在在VerUnion數組中將以數組中將以頂點頂點j所在的連通分量的每所在的連通分量的每個頂點個頂點為下標的元素值設為為下標的元素值設為VerUnioni;3.重復執行1、2步，直至最小生成樹中的邊數為VerNum-112001280051001

8、21601614023120342203618045250462401234560123456Fijw001281051001216016140231203422036180452504624012340601224060122401011140101111010000000.0562341102522121614AdjUnionVerUnion#define MAX_VER_NUM 10/頂點個數最大值頂點個數最大值#define MAX 10000int VerNum;/頂點個數頂點個數int AdjNum;/邊的個數邊的個數int Edge MAX_VER_NUM MAX_VER_NUM

9、 ;/圖的鄰接矩陣圖的鄰接矩陣void Kruskal( ) /假設圖的鄰接矩陣、頂點個數、邊的個數這些信息已經讀進來了假設圖的鄰接矩陣、頂點個數、邊的個數這些信息已經讀進來了int* VerUnion = new intVerNum;int (*AdjUnion)4 = new intAdjNum4;for(int i=0; iVerNum; i+)VerUnioni=i;/構造頂點數組構造頂點數組,值相同表示在同一個連通分量上值相同表示在同一個連通分量上int j=0, k=0;for(i=0; iVerNum-1; i+) /構造邊的數組構造邊的數組for(j=i+1; jVerNum;

10、 j+)if(G.AdjMatrixijMAX)/0:邊還未檢測過邊還未檢測過,1:邊已經加進來了邊已經加進來了-1:檢測過但因為在同一個連通分量上，被舍去了檢測過但因為在同一個連通分量上，被舍去了AdjUnionk0=0;AdjUnionk1=i;AdjUnionk2=j;AdjUnionk3=G.AdjMatrixij;k+;j=0; int count=0;while(countVerNum-1)int min=MAX;for(k=0;kAdjNum;k+) /找到權值最小的邊找到權值最小的邊AdjUnionj;if(AdjUnionk0=0 & AdjUnionk3min) m

11、in=AdjUnionk3; j=k;/判斷判斷AdjUnionj這條邊的這條邊的2個頂點是不是在同一個連通分量上個頂點是不是在同一個連通分量上if(VerUnion AdjUnionj1 !=VerUnion AdjUnionj2 )/如果不是如果不是,輸出來輸出來,設置標志位設置標志位/重新設置在同一個連通分量上的頂點的標記值重新設置在同一個連通分量上的頂點的標記值cout AdjUnionj1 AdjUnionj2 AdjUnionj3 endl;AdjUnionj0=1;int tmp=VerUnion AdjUnionj2 ;for(k=0; kVerNum; k+)if(VerUn

12、ionk=tmp)VerUnionk=VerUnion AdjUnionj1 ;count+;else AdjUnionj0=-1; /如果是，舍去，重來如果是，舍去，重來(1)(2)15整個算法的時間復雜性是整個算法的時間復雜性是O(n2)163 普里姆算法 先看例子。 普里姆算法的() ：1. 從連通網絡從連通網絡 N = V, E 中的某一頂點中的某一頂點 u0出發，選擇出發，選擇與它關聯的具有最小權值的邊與它關聯的具有最小權值的邊(u0, v)，將其頂點加入，將其頂點加入到生成樹的頂點集合到生成樹的頂點集合U中。中。2. 以后每一步從一個頂點在以后每一步從一個頂點在U中，而另一個頂點不

13、在中，而另一個頂點不在U中的各條邊中選擇權值最小的邊中的各條邊中選擇權值最小的邊(u, v),把它的頂點加把它的頂點加入到集合入到集合U中。如此繼續下去，直到網絡中的所有頂中。如此繼續下去，直到網絡中的所有頂點都加入到生成樹頂點集合點都加入到生成樹頂點集合U中為止。中為止。1705623428110252422181216140510425322212116614在Prim算法運算過程當中，需要知道哪些信息？1.V集合內各頂點距離U內權值最小的邊的權值；2. V集合內各頂點距離U內哪個頂點最近(權值最小)。U：當前生成樹頂點集合，V：不屬于當前生成樹的頂點集合。18 采用采用來存儲圖。為了實現

14、上述思想，必須定義來存儲圖。為了實現上述思想，必須定義2個個輔助數組：輔助數組： 存放頂點集合存放頂點集合 ()內的各頂點到頂點集合內的各頂點到頂點集合U(生成樹頂點集合生成樹頂點集合)內的權值最小的邊的權值。內的權值最小的邊的權值。 記錄頂點集合記錄頂點集合 ()內的各頂點距離頂點集合內的各頂點距離頂點集合()內內哪個頂點哪個頂點最近（權值最小）。最近（權值最?。?。 從頂點從頂點0出發，出發，2個輔助數組的初始狀態為：個輔助數組的初始狀態為：0 28 10 lowcost0123456-1 000000nearvex0123456V=5選邊選邊(0,5) 因為在生成樹頂點集合內最初只有一個頂

15、點因為在生成樹頂點集合內最初只有一個頂點0，因此在，因此在nearvex數組中，只有表示頂點數組中，只有表示頂點0的數組元素的數組元素nearvex0=-1，其他都是，其他都是0，表，表示集合外各頂點距離集合內最近的頂點是示集合外各頂點距離集合內最近的頂點是0。 數組數組lowcost表示生成樹頂點集合（目前只有頂點表示生成樹頂點集合（目前只有頂點0）頂點到生）頂點到生成樹外各頂點的邊的最小權值。初始值為鄰接矩陣中頂點成樹外各頂點的邊的最小權值。初始值為鄰接矩陣中頂點0所在的行。所在的行。19在在prim算法里要重復做以下工作算法里要重復做以下工作()：。20在在prim算法里要重復做以下工作

16、算法里要重復做以下工作()：。則選中的權值最小的邊為。則選中的權值最小的邊為(nearvexv,v)，相應的權值為，相應的權值為lowcostv。如第一次選中的。如第一次選中的v=5，則邊，則邊(0,5)是選中的權值最小的是選中的權值最小的邊，相應的權值為邊，相應的權值為lowcost5=10。，將，將邊邊(nearvexv, v, lowcostv)輸出來。輸出來。：注意，原來頂點注意，原來頂點v不屬于生成樹頂點集合，現在不屬于生成樹頂點集合，現在v加入進來了，則加入進來了，則頂點集合頂點集合V(生成樹外生成樹外)內的各頂點到頂點集合內的各頂點到頂點集合U(生成樹頂點集合生成樹頂點集合)內的

17、權值最小的邊的權值內的權值最小的邊的權值lowcosti=minlowcosti, Edgevi，即用，即用V集合內各頂點集合內各頂點i到到加入集合加入集合U的新頂點的新頂點v的距離的距離(Edgevi)與原來它們到集合與原來它們到集合U中頂中頂點的最短距離點的最短距離(lowcosti)做比較，取距離近的，作為這些集合外做比較，取距離近的，作為這些集合外頂點到生成樹頂點集合內頂點的最短距離。頂點到生成樹頂點集合內頂點的最短距離。：如果頂點集合：如果頂點集合V內頂點內頂點i到頂點到頂點v的距離比原來它的距離比原來它到頂點集合到頂點集合U中頂點的最短距離還要近，則修改中頂點的最短距離還要近，則修

18、改nearvexi：nearvexi=v；表示生成樹外頂點；表示生成樹外頂點i到生成樹內頂點到生成樹內頂點v當前距離最當前距離最近。近。21024181402510242502218220121201614160281028005623428110252422181216140 28 25 10 lowcost-1 0005 -1 0nearvexV=4, 選邊選邊(5,4)0 28 22 25 10 24 lowcost-1 004 -1 -1 4nearvexV=3, 選邊選邊(4,3)0 28 12 22 25 10 18 lowcost-1 03 -1 -1 -1 3nearvexV=

19、2, 選邊選邊(3,2)0 16 12 22 25 10 18 lowcost-1 2 -1 -1 -1 -1 3nearvexV=1, 選邊選邊(2,1)0 16 12 22 25 10 14 lowcost-1 -1 -1 -1 -1 -1 1nearvexV=6, 選邊選邊(1,6)0 16 12 22 25 10 14 lowcost-1 -1 -1 -1 -1 -1 -1nearvex0 28 10 lowcost0123456-1 000000nearvex0123456V=5, 選邊選邊(0,5)深色背景：深色背景：U內的頂點內的頂點粗體粗體被修改的值被修改的值056234281

20、10252422181216140510425322212116614白色背景：白色背景：V中的頂點中的頂點淺色背景：淺色背景：V中將被選擇的頂點中將被選擇的頂點23#define MAX 100000#define MAX_VER_NUM 10/頂點個數最大值頂點個數最大值int Edge MAX_VER_NUM MAX_VER_NUM ; /鄰接矩陣鄰接矩陣int vernum;/頂點個數頂點個數/假設鄰接矩陣和頂點個數已經讀進來了假設鄰接矩陣和頂點個數已經讀進來了void Prim( )int* lowcost = new intvernum;int* nearvex = new intvernum;for(int i=0; iverNum; i+)lowcosti = Edge0i;nearvexi=0;nearvex0 = -1;for(i=1; iverNum; i+)int min=MAX;int v=0;24for(int j=0