第6章專題3-最小生成樹(shù)1

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

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

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

4、生成子樹(shù)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ì)頂頂點(diǎn)點(diǎn)集集UVUuvvu頂頂點(diǎn)點(diǎn)集集T1T26.3 最小生成樹(shù)最小生成樹(shù) 當(dāng)將邊當(dāng)將邊(u，v)加入加入T中時(shí)，由生成樹(shù)的定義，中時(shí)，由生成樹(shù)的定義，T中必存在一中必存在一條包含邊條包含邊(u，v)的回路，刪去邊的回路，刪去邊(u，v)便可消除上述回路，便可消除上述回路，同時(shí)得到另一棵生成樹(shù)同時(shí)得到另一棵生成樹(shù)T 。因?yàn)檫?。因?yàn)檫?u，v)的權(quán)值小于等于邊的權(quán)值小于

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

6、同時(shí)，同時(shí)v并入并入U(xiǎn)，直至，直至U=V。普里姆（普里姆（Prim）算法算法 6.3 最小生成樹(shù)最小生成樹(shù)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ù)最小生成樹(shù)數(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ù)最小生成樹(shù)數(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ù)最小生成樹(shù)數(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ù)最小生成樹(shù)數(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ù)最小生成樹(shù)數(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ù)最小生成樹(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社1. 圖的存儲(chǔ)結(jié)構(gòu)：由于在算法執(zhí)行過(guò)程中，需要不斷圖的存儲(chǔ)結(jié)構(gòu)：由于在算法執(zhí)行過(guò)程中，需要不斷讀取任意兩個(gè)頂點(diǎn)之間邊的權(quán)值，所以，圖采用鄰接讀取任意兩個(gè)頂點(diǎn)之間邊的權(quán)值，所以，圖采用鄰接矩陣存儲(chǔ)。矩陣存儲(chǔ)。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)6.3 最小生成樹(shù)最小生成樹(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社251234192646381725ABEDCF例如，對(duì)于頂點(diǎn)例如，對(duì)于

10、頂點(diǎn)C，只需保留，只需保留minarcAC, arcFC 6.3 最小生成樹(shù)最小生成樹(shù)2. 候選最短邊集：設(shè)置數(shù)組候選最短邊集：設(shè)置數(shù)組shortEdgen表示候選最表示候選最短邊集，數(shù)組元素包括短邊集，數(shù)組元素包括adjvex和和lowcost兩個(gè)域，分別兩個(gè)域，分別表示候選最短邊的鄰接點(diǎn)和權(quán)值。表示候選最短邊的鄰接點(diǎn)和權(quán)值。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)對(duì)于對(duì)于V-U中的每個(gè)頂點(diǎn)，只保留從中的每個(gè)頂點(diǎn)，只保留從該頂點(diǎn)到該頂點(diǎn)到U中某頂點(diǎn)的最短邊。中某頂點(diǎn)的最短邊。數(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 最小生成樹(shù)最小生成樹(shù)shortEdgei.adjvex = kshortEdgei.lowcost = w數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)shortEdgej.lowcost = min shortEdgej.lowcost , cost(vj，vk)shortEdgej.adjvex = k（如果邊（如果邊(vj，vk)的權(quán)值較?。┑臋?quán)值較小）p 頂點(diǎn)頂點(diǎn)vk從集合從集合V-U進(jìn)入集合進(jìn)入集合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. 輸出頂點(diǎn)輸出頂點(diǎn)v，將頂點(diǎn)，將頂點(diǎn)v加入集合加入集合U中；中；3. 重復(fù)執(zhí)行下列操作重復(fù)執(zhí)行下列操作n-1次次 3.1 在在shortEdgen.lowcost中選取最短邊及對(duì)應(yīng)的中選取最短邊及對(duì)應(yīng)的鄰接點(diǎn)編號(hào)鄰接點(diǎn)編號(hào)k； 3.2 輸出頂點(diǎn)輸出頂點(diǎn)k和對(duì)應(yīng)的權(quán)值；和對(duì)應(yīng)的權(quán)值； 3.3 將頂點(diǎn)將頂點(diǎn)k加入集合加入集合U中；中； 3.4 調(diào)整數(shù)組調(diào)整數(shù)組shortEdgen；Prim算法算法偽代碼偽代碼 6.3 最小生成樹(shù)最小生成樹(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社Prim算法算法運(yùn)行過(guò)程運(yùn)行過(guò)程

13、 6.3 最小生成樹(shù)最小生成樹(shù)數(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; /將頂點(diǎn)將頂點(diǎn)0加入集合加入集合U for (i = 1; i G.vertexNum; i+) k = MinEdge(shortEdge, G.vertexNum) /尋找最短邊的鄰接點(diǎn)尋找最短邊的鄰接

14、點(diǎn)k cout(k shortEdgek.adjvex) shortEdgek.lowcost; shortEdgek.lowcost = 0; /將頂點(diǎn)將頂點(diǎn)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ù)最小生成樹(shù)數(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 最小生成樹(shù)最小生成樹(shù)時(shí)間復(fù)雜度？時(shí)間復(fù)雜度？O(n)O(n)O(n)因此，算法的時(shí)間復(fù)雜度為因此，算法的時(shí)間復(fù)雜度為O(n2)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社克魯斯卡爾（克魯斯卡爾（Kruskal）算法）算法 基本思想基本思想：設(shè)無(wú)向連通網(wǎng)為：設(shè)無(wú)向連通網(wǎng)為G(V, E)，令，令G的最小生成樹(shù)為的最小生成樹(shù)為T(U, TE)，其，其初態(tài)為初態(tài)為UV，TE ，然后，按照，然后，按照邊的權(quán)值邊的權(quán)值由小到大的

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

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

19、；6.3 最小生成樹(shù)最小生成樹(shù)Kruskal算法的基本思想用偽代碼描述如下：算法的基本思想用偽代碼描述如下： 關(guān)鍵：如何判別被考察邊的兩個(gè)頂點(diǎn)是否位于兩個(gè)連通分量關(guān)鍵：如何判別被考察邊的兩個(gè)頂點(diǎn)是否位于兩個(gè)連通分量 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社251234192646381725ABEDCFABEDCF連通分量連通分量A, B, C, D, E, F6.3 最小生成樹(shù)最小生成樹(shù)數(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ù)最小生成樹(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社251234192646381725ABEDCFABEDCF12176.3 最小生成樹(shù)最小生成樹(shù)連通分量連通分量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 最小生成樹(shù)最小生成樹(shù)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ù)最小生成樹(shù)數(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ù)最小生成樹(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社6.3 最小生成樹(shù)最小生成樹(shù)1. 圖的存儲(chǔ)結(jié)構(gòu)：因?yàn)閳D的存儲(chǔ)結(jié)構(gòu)

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

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

24、成樹(shù)的根結(jié)點(diǎn)只需沿?cái)?shù)組所在生成樹(shù)的根結(jié)點(diǎn)只需沿?cái)?shù)組v = parentv不不斷查找斷查找v的雙親，直到的雙親，直到parentv等于等于-1。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社6.3 最小生成樹(shù)最小生成樹(shù)1. 初始化輔助數(shù)組初始化輔助數(shù)組parentn；num = 0；2. 依次考查每一條邊依次考查每一條邊f(xié)or (i = 0; i arcNum; i+) 2.1 vex1 = edgei.from所在生成樹(shù)的根結(jié)點(diǎn)；所在生成樹(shù)的根結(jié)點(diǎn)； 2.2 vex2 = edgei.to所在生成樹(shù)的根結(jié)點(diǎn)；所在生成樹(shù)的根結(jié)點(diǎn)； 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算法用偽代碼進(jìn)一步描述為：算法用偽代碼進(jìn)一步描述為： Kruskal算法算法偽代碼偽代碼數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社v1初始化：初始化：parent0=-1parent1=-1parent2=-1parent3=-1parent4=-1parent5=-16.3 最小生成樹(shù)最小生成樹(shù)v5v0v4v3v2Kruskal算法算法運(yùn)行過(guò)程運(yùn)行過(guò)程數(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 最小生成樹(shù)最小生成樹(shù)v5v0v4v3v212Kruskal算法算法運(yùn)行過(guò)程運(yùn)行過(guò)程1v1數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社考察最短邊考察最短邊(v2, v3):parent0=-1parent1=-1parent2=-1parent3=-1parent4=1parent5=-16.3 最小生成樹(shù)最小生成樹(shù)v5v0v4v31712Kruskal算法算法運(yùn)行過(guò)程運(yùn)行過(guò)程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 最小生成樹(shù)最小生成樹(shù)v5v4v3171219v1v1v2Kruskal算法算法運(yùn)行過(guò)程運(yùn)行過(guò)程0v0數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社考察最短邊考察最短邊(v2, v5):parent0=-1parent1=-1parent2=-1parent3=2parent4=1parent5=06.3 最小生成樹(shù)最小生成樹(shù)Kruskal算法算法運(yùn)行過(guò)程運(yùn)行過(guò)程

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 最小生成樹(shù)最小生成樹(shù)考查邊考查邊(v3, v5)，由于，由于parent3=2，parent2=-1，則則v3所在生成樹(shù)的根結(jié)點(diǎn)是所在生成樹(shù)的根結(jié)點(diǎn)是v2 ，而而parent5=0，parent0=2，則，則v5所在生成樹(shù)的所在生成樹(shù)的根結(jié)點(diǎn)也是根結(jié)點(diǎn)也是v2 ，故舍去此邊。，故舍去此邊。Kruskal算法算法運(yùn)行過(guò)程運(yùn)行過(guò)程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 最小生成樹(shù)最小生成樹(shù)Kruskal算法算法運(yùn)行過(guò)程運(yùn)行過(guò)程v5v4v3171219v1v1v2v012526數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C版）版）清華大學(xué)出版社清華大學(xué)出版社6.3 最小生成樹(shù)最小生成樹(shù)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