第6章專題3-最小生成樹1

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社專題專題3：最小生成樹：最小生成樹123最小生成樹的定義最小生成樹的定義 Prim算法算法 Kruskal算法算法 4MST性質(zhì)性質(zhì)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社p 生生成樹的代價：成樹的代價：設(shè)設(shè)G = (V, E)是一個無向連通網(wǎng)，生是一個無向連通網(wǎng)，生成樹上各邊的權(quán)值之和稱為該成樹上各邊的權(quán)值之和稱為該生生成樹的代價成樹的代價。 p 最小生成樹：最小生成樹：在圖在圖G所有生成樹中，代價最小的生所有生成樹中，代價最小的生成樹稱為成樹稱為最小生成樹最小生成樹。 6.3 最小生成樹最小生成樹最小生成樹的定義最

2、小生成樹的定義最小生成樹的概念可以應(yīng)用到許多實際問題中。最小生成樹的概念可以應(yīng)用到許多實際問題中。例：在例：在n個城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)個城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條條通信線路，而每兩個城市之間架設(shè)通信線路的造價是通信線路，而每兩個城市之間架設(shè)通信線路的造價是不一樣的，那么如何設(shè)計才能使得總造價最?。坎灰粯拥?，那么如何設(shè)計才能使得總造價最?。?數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社MST性質(zhì)性質(zhì)假設(shè)假設(shè)G=(V, E)是一個無向連通網(wǎng)，是一個無向連通網(wǎng)，U是頂點集是頂點集V的一的一個非空子集。若個非空子集。若(u, v)是一條具有最小權(quán)值的邊，其是一條

3、具有最小權(quán)值的邊，其中中uU，vVU，則必存在一棵包含邊，則必存在一棵包含邊(u, v)的最的最小生成樹。小生成樹。頂頂點點集集UVUuvvu頂頂點點集集T1T26.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社MST性質(zhì)性質(zhì)頂頂點點集集UVUuvvu頂頂點點集集T1T26.3 最小生成樹最小生成樹設(shè)設(shè)T是圖是圖G的一棵最小生成樹，將的一棵最小生成樹，將T中的頂點集分成兩部分：中的頂點集分成兩部分：頂點集頂點集U：U和相關(guān)的邊構(gòu)成一棵最小生成子樹和相關(guān)的邊構(gòu)成一棵最小生成子樹T1；頂點集頂點集V-U：V-U和相關(guān)的邊構(gòu)成一棵最小生成子樹和相關(guān)的邊構(gòu)成一棵最小

4、生成子樹T2。 則則T1和和T2之間只能有一條邊，不妨設(shè)為之間只能有一條邊，不妨設(shè)為(u，v)，且，且u和和u之間、之間、v和和v之間均是連通的之間均是連通的數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社MST性質(zhì)性質(zhì)頂頂點點集集UVUuvvu頂頂點點集集T1T26.3 最小生成樹最小生成樹 當(dāng)將邊當(dāng)將邊(u，v)加入加入T中時，由生成樹的定義，中時，由生成樹的定義，T中必存在一中必存在一條包含邊條包含邊(u，v)的回路，刪去邊的回路，刪去邊(u，v)便可消除上述回路，便可消除上述回路，同時得到另一棵生成樹同時得到另一棵生成樹T 。因為邊。因為邊(u，v)的權(quán)值小于等于邊的權(quán)值小于

5、等于邊(u，v)的權(quán)值，則的權(quán)值，則T 的代價亦小于等于的代價亦小于等于T的代價，則的代價，則T 是一是一棵最小生成樹，且包含邊棵最小生成樹，且包含邊(u，v)。這與假設(shè)矛盾，由此性質(zhì)得。這與假設(shè)矛盾，由此性質(zhì)得證證數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社基本思想基本思想：設(shè)：設(shè)G=(V, E)是一個連通網(wǎng)，是一個連通網(wǎng)，T=(U, TE)是是G的最小的最小生成樹，生成樹，T的的初始狀態(tài)初始狀態(tài)為為U=u0（u0V），），TE= ，重復(fù)執(zhí)，重復(fù)執(zhí)行下述操作：在所有行下述操作：在所有uU，vV-U的邊中找一條代價最小的的邊中找一條代價最小的邊邊(u, v)并入集合并入集合TE，

6、同時，同時v并入并入U，直至，直至U=V。普里姆（普里姆（Prim）算法算法 6.3 最小生成樹最小生成樹Prim算法的基本思想用偽代碼描述如下：算法的基本思想用偽代碼描述如下：1. 初始化：初始化：U = v0； TE= ； 2. 重復(fù)下述操作直到重復(fù)下述操作直到U = V： 2.1 在在E中尋找最短邊中尋找最短邊(u，v)，且滿足，且滿足uU，vV-U； 2.2 U = U + v； 2.3 TE = TE + (u，v)；關(guān)鍵關(guān)鍵:是如何找到連接是如何找到連接U和和V-U的最短邊的最短邊。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社U=A V-U=B, C, D, E,

7、Fcost=(A, B)34, (A, C)46, (A, D),(A, E),(A, F)19 251234192646381725ABEDCFPrim算法算法 6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社Prim算法算法 251234192646381725ABEDCFU=A, F V-U=B, C, D, Ecost=(A, B)34,(F, C)25, (F, D)25,(F, E)26 6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社Prim算法算法 2512341926381725ABEDCFU=A,

8、F, C V-U=B, D, Ecost=(A, B)34, (C, D)17,(F, E)26 6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社Prim算法算法 12341926381725ABEDCFU=A, F, C, D V-U=B, Ecost=(A, B)34, (F, E)26 6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社Prim算法算法 123419261725ABEDCFU=A, F, C, D, E V-U=Bcost=(E, B)12 6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）

9、清華大學(xué)出版社清華大學(xué)出版社Prim算法算法 1219261725ABEDCFU=A, F, C, D, E, B V-U= 6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社1. 圖的存儲結(jié)構(gòu)：由于在算法執(zhí)行過程中，需要不斷圖的存儲結(jié)構(gòu)：由于在算法執(zhí)行過程中，需要不斷讀取任意兩個頂點之間邊的權(quán)值，所以，圖采用鄰接讀取任意兩個頂點之間邊的權(quán)值，所以，圖采用鄰接矩陣存儲。矩陣存儲。數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社251234192646381725ABEDCF例如，對于頂點例如，對于

10、頂點C，只需保留，只需保留minarcAC, arcFC 6.3 最小生成樹最小生成樹2. 候選最短邊集：設(shè)置數(shù)組候選最短邊集：設(shè)置數(shù)組shortEdgen表示候選最表示候選最短邊集，數(shù)組元素包括短邊集，數(shù)組元素包括adjvex和和lowcost兩個域，分別兩個域，分別表示候選最短邊的鄰接點和權(quán)值。表示候選最短邊的鄰接點和權(quán)值。 數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計對于對于V-U中的每個頂點，只保留從中的每個頂點，只保留從該頂點到該頂點到U中某頂點的最短邊。中某頂點的最短邊。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社p 候選最短邊候選最短邊(vi, vk)的權(quán)值為的權(quán)值為w，其中，其中vi

11、V-U，vkU：如何用如何用lowcost和和adjvex表示候選最短邊集表示候選最短邊集？6.3 最小生成樹最小生成樹shortEdgei.adjvex = kshortEdgei.lowcost = w數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計shortEdgej.lowcost = min shortEdgej.lowcost , cost(vj，vk)shortEdgej.adjvex = k（如果邊（如果邊(vj，vk)的權(quán)值較?。┑臋?quán)值較?。﹑ 頂點頂點vk從集合從集合V-U進入集合進入集合U后，依據(jù)下式更新數(shù)組后，依據(jù)下式更新數(shù)組shortEdge： 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清

12、華大學(xué)出版社1. 初始化輔助數(shù)組初始化輔助數(shù)組shortEdgen；2. 輸出頂點輸出頂點v，將頂點，將頂點v加入集合加入集合U中；中；3. 重復(fù)執(zhí)行下列操作重復(fù)執(zhí)行下列操作n-1次次 3.1 在在shortEdgen.lowcost中選取最短邊及對應(yīng)的中選取最短邊及對應(yīng)的鄰接點編號鄰接點編號k； 3.2 輸出頂點輸出頂點k和對應(yīng)的權(quán)值；和對應(yīng)的權(quán)值； 3.3 將頂點將頂點k加入集合加入集合U中；中； 3.4 調(diào)整數(shù)組調(diào)整數(shù)組shortEdgen；Prim算法算法偽代碼偽代碼 6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社Prim算法算法運行過程運行過程

13、 6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社void Prim(MGraph G) for (i = 1; i G.vertexNum; i+) /初始化輔助數(shù)組初始化輔助數(shù)組shortEdge shortEdgei.lowcost = G.arc0i; shortEdgei.adjvex = 0; shortEdge0.lowcost = 0; /將頂點將頂點0加入集合加入集合U for (i = 1; i G.vertexNum; i+) k = MinEdge(shortEdge, G.vertexNum) /尋找最短邊的鄰接點尋找最短邊的鄰接

14、點k cout(k shortEdgek.adjvex) shortEdgek.lowcost; shortEdgek.lowcost = 0; /將頂點將頂點k加入集合加入集合U中中 for (j = 1; j G.vertexNum; j+) /調(diào)整數(shù)組調(diào)整數(shù)組shortEdgen if G.arckj shortEdgej.lowcost shortEdgej.lowcost = G.arckj; shortEdgej.adjvex = k; Prim算法算法C+描述描述 6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社void Prim(MGrap

15、h G) for (i = 1; i G.vertexNum; i+) shortEdgei.lowcost = G.arc0i; shortEdgei.adjvex = 0; shortEdge0.lowcost = 0; for (i = 1; i G.vertexNum; i+) k = MinEdge(shortEdge, G.vertexNum) cout(k shortEdgek.adjvex) shortEdgek.lowcost; shortEdgek.lowcost = 0; for (j = 1; j G.vertexNum; j+) if G.arckj shortEdg

16、ej.lowcost shortEdgej.lowcost = G.arckj; shortEdgej.adjvex = k; Prim算法算法C+描述描述 6.3 最小生成樹最小生成樹時間復(fù)雜度？時間復(fù)雜度？O(n)O(n)O(n)因此，算法的時間復(fù)雜度為因此，算法的時間復(fù)雜度為O(n2)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社克魯斯卡爾（克魯斯卡爾（Kruskal）算法）算法 基本思想基本思想：設(shè)無向連通網(wǎng)為：設(shè)無向連通網(wǎng)為G(V, E)，令，令G的最小生成樹為的最小生成樹為T(U, TE)，其，其初態(tài)為初態(tài)為UV，TE ，然后，按照，然后，按照邊的權(quán)值邊的權(quán)值由小到大的

17、順序由小到大的順序，考察，考察G的邊集的邊集E中的各條邊。若被考察的邊中的各條邊。若被考察的邊的兩個頂點屬于的兩個頂點屬于T的兩個不同的的兩個不同的連通分量連通分量，則將此邊作為最小，則將此邊作為最小生成樹的邊加入到生成樹的邊加入到T中，同時把兩個連通分量連接為一個連通中，同時把兩個連通分量連接為一個連通分量；若被考察邊的兩個頂點屬于同一個連通分量，則舍去分量；若被考察邊的兩個頂點屬于同一個連通分量，則舍去此邊，以免造成回路，如此下去，當(dāng)此邊，以免造成回路，如此下去，當(dāng)T中的連通分量個數(shù)為中的連通分量個數(shù)為1時，此連通分量便為時，此連通分量便為G的一棵最小生成樹。的一棵最小生成樹。 6.3 最

18、小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社克魯斯卡爾（克魯斯卡爾（Kruskal）算法）算法 1. 初始化：初始化：U=V；TE= ； 2. 重復(fù)下述操作直到重復(fù)下述操作直到T中的連通分量個數(shù)為中的連通分量個數(shù)為1： 2.1 在在E中尋找最短邊中尋找最短邊(u，v); 2.2 如果頂點如果頂點u、v位于位于T的兩個不同連通分量，則的兩個不同連通分量，則 2.2.1 將邊將邊(u，v)并入并入TE； 2.2.2 將這兩個連通分量合為一個；將這兩個連通分量合為一個； 2.3 標(biāo)記邊標(biāo)記邊(u，v)，使得，使得(u，v)不參加后續(xù)最短邊的選?。徊粎⒓雍罄m(xù)最短邊的選取

19、；6.3 最小生成樹最小生成樹Kruskal算法的基本思想用偽代碼描述如下：算法的基本思想用偽代碼描述如下： 關(guān)鍵：如何判別被考察邊的兩個頂點是否位于兩個連通分量關(guān)鍵：如何判別被考察邊的兩個頂點是否位于兩個連通分量 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社251234192646381725ABEDCFABEDCF連通分量連通分量A, B, C, D, E, F6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社251234192646381725ABEDCFABEDCF連通分量連通分量A, B, C, D, E, F12連通分量連通分量A,

20、 B, E, C, D, F6.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社251234192646381725ABEDCFABEDCF12176.3 最小生成樹最小生成樹連通分量連通分量A, B, E, C, D,F連通分量連通分量A, B, E, C, D, F數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社251234192646381725ABEDCFABEDCF12196.3 最小生成樹最小生成樹17連通分量連通分量A, B, E, C, D, F連通分量連通分量A, F, B, E, C, D數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版

21、社清華大學(xué)出版社251234192646381725ABEDCFABEDCF連通分量連通分量A, F, B, E, C, D12連通分量連通分量A, F, C, D, B, E1917256.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社251234192646381725ABEDCFABEDCF連通分量連通分量A, F, C, D, B, E12連通分量連通分量A, F, C, D, B, E191725266.3 最小生成樹最小生成樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社6.3 最小生成樹最小生成樹1. 圖的存儲結(jié)構(gòu)：因為圖的存儲結(jié)構(gòu)

22、：因為Kruskal算法是依次對圖中的算法是依次對圖中的邊進行操作，因此考慮用邊集數(shù)組存儲圖中的邊，為邊進行操作，因此考慮用邊集數(shù)組存儲圖中的邊，為了提高查找速度，將邊集數(shù)組按邊上的權(quán)排序。了提高查找速度，將邊集數(shù)組按邊上的權(quán)排序。 數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社6.3 最小生成樹最小生成樹2. 連通分量。連通分量。Kruskal算法實質(zhì)上是使生成樹以一種隨意的方算法實質(zhì)上是使生成樹以一種隨意的方式生長，初始時每個頂點構(gòu)成一棵生成樹，然后每生長一次就式生長，初始時每個頂點構(gòu)成一棵生成樹，然后每生長一次就將兩棵樹合并，到最后合并成一棵樹。將兩棵

23、樹合并，到最后合并成一棵樹。 設(shè)數(shù)組設(shè)數(shù)組parentn，元素，元素parenti表示頂點表示頂點i的雙親結(jié)點，初的雙親結(jié)點，初始時，始時，parenti= -1，表示頂點，表示頂點i沒有雙親，即該結(jié)點是所在生沒有雙親，即該結(jié)點是所在生成樹的根結(jié)點；對于邊成樹的根結(jié)點；對于邊(u, v)，設(shè)，設(shè)vex1和和vex2分別表示兩個頂分別表示兩個頂點點u和和v所在生成樹的根結(jié)點，如果所在生成樹的根結(jié)點，如果vex1vex2，則頂點，則頂點u和和v必必位于不同的連通分量，令位于不同的連通分量，令parentvex2 = vex1，實現(xiàn)將兩棵生，實現(xiàn)將兩棵生成樹合并。成樹合并。 求某頂點求某頂點v所在生

24、成樹的根結(jié)點只需沿數(shù)組所在生成樹的根結(jié)點只需沿數(shù)組v = parentv不不斷查找斷查找v的雙親，直到的雙親，直到parentv等于等于-1。 數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社6.3 最小生成樹最小生成樹1. 初始化輔助數(shù)組初始化輔助數(shù)組parentn；num = 0；2. 依次考查每一條邊依次考查每一條邊f(xié)or (i = 0; i arcNum; i+) 2.1 vex1 = edgei.from所在生成樹的根結(jié)點；所在生成樹的根結(jié)點； 2.2 vex2 = edgei.to所在生成樹的根結(jié)點；所在生成樹的根結(jié)點； 2.3 如果如果vex1

25、!= vex2，執(zhí)行下述操作：，執(zhí)行下述操作： 2.3.1 parentvex2 = vex1; 2.3.2 num+; 2.3.3 if (num = n-1) 算法結(jié)束；算法結(jié)束；Kruskal算法用偽代碼進一步描述為：算法用偽代碼進一步描述為： Kruskal算法算法偽代碼偽代碼數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社v1初始化：初始化：parent0=-1parent1=-1parent2=-1parent3=-1parent4=-1parent5=-16.3 最小生成樹最小生成樹v5v0v4v3v2Kruskal算法算法運行過程運行過程數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）

26、清華大學(xué)出版社清華大學(xué)出版社v1考察最短邊考察最短邊(v1, v4):parent0=-1parent1=-1parent2=-1parent3=-1parent4=-1parent5=-16.3 最小生成樹最小生成樹v5v0v4v3v212Kruskal算法算法運行過程運行過程1v1數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社考察最短邊考察最短邊(v2, v3):parent0=-1parent1=-1parent2=-1parent3=-1parent4=1parent5=-16.3 最小生成樹最小生成樹v5v0v4v31712Kruskal算法算法運行過程運行過程2v1v1

27、v2數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社考察最短邊考察最短邊(v0, v5):parent0=-1parent1=-1parent2=-1parent3=2parent4=1parent5=-16.3 最小生成樹最小生成樹v5v4v3171219v1v1v2Kruskal算法算法運行過程運行過程0v0數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社考察最短邊考察最短邊(v2, v5):parent0=-1parent1=-1parent2=-1parent3=2parent4=1parent5=06.3 最小生成樹最小生成樹Kruskal算法算法運行過程運行過程

28、v5v4v3171219v1v1v2v0225數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社考察最短邊考察最短邊(v3, v5):parent0=2parent1=-1parent2=-1parent3=2parent4=1parent5=06.3 最小生成樹最小生成樹考查邊考查邊(v3, v5)，由于，由于parent3=2，parent2=-1，則則v3所在生成樹的根結(jié)點是所在生成樹的根結(jié)點是v2 ，而而parent5=0，parent0=2，則，則v5所在生成樹的所在生成樹的根結(jié)點也是根結(jié)點也是v2 ，故舍去此邊。，故舍去此邊。Kruskal算法算法運行過程運行過程v5v4v

29、3171219v1v1v2v02525數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社考察最短邊考察最短邊(v4, v5):parent0=2parent1=-1parent2=-1parent3=2parent4=1parent5=06.3 最小生成樹最小生成樹Kruskal算法算法運行過程運行過程v5v4v3171219v1v1v2v012526數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社6.3 最小生成樹最小生成樹Kruskal算法算法C+描述描述void Kruskal(EdgeGraph G) for (i = 0; i G.vertexNum; i+) parenti = -1; for (num = 0, i = 0; i G.edgeNum; i+) vex1 = FindRoot(parent, G.edgei.from); vex2 = FindRoot(parent, G.edgei.to); if (vex1 != v