數(shù)據(jù)結(jié)構(gòu)主講人：楊丹常州信息職業(yè)技術(shù)學(xué)院5.5最小生成樹(shù)Part01最小生成樹(shù)概念如果連通圖G的一個(gè)子圖是一棵包含G的所有頂點(diǎn)的樹(shù)，則該子圖稱(chēng)為G的生成樹(shù)。生成樹(shù)最小生成樹(shù)圖G及其兩棵生成樹(shù)如果無(wú)向連通圖是一個(gè)帶權(quán)圖，那么它的所有生成樹(shù)中必有一棵邊的權(quán)值總和最小的生成樹(shù)，這棵生成樹(shù)稱(chēng)為最小代價(jià)生成樹(shù)，簡(jiǎn)稱(chēng)最小生成樹(shù)。最小生成樹(shù)最小生成樹(shù)從最小生成樹(shù)的定義可知，構(gòu)造有n個(gè)頂點(diǎn)的無(wú)向連通帶權(quán)圖的最小生成樹(shù)，必須滿足以下三個(gè)條件：(1)構(gòu)造的最小生成樹(shù)必須包括n個(gè)頂點(diǎn)；(2)構(gòu)造的最小生成樹(shù)中有且僅有n-1條邊；(3)構(gòu)造的最小生成樹(shù)中不能存在回路。說(shuō)明Part02Prim算法Prim算法思想假設(shè)G=(V,E)是一個(gè)無(wú)向帶權(quán)圖，其中V是帶權(quán)圖中頂點(diǎn)的集合，E是邊的權(quán)值集合。設(shè)置兩個(gè)新的集合U和TE，其中U用來(lái)存放帶權(quán)圖G的最小生成樹(shù)的頂點(diǎn)集合，TE用來(lái)存放帶權(quán)圖G的最小生成樹(shù)邊的集合。132+初始化：U={u0},TE={Φ},u0是圖G中任意一個(gè)頂點(diǎn)；+如果U=V，則算法結(jié)束，否則重復(fù)步驟2+在所有u∈U,v∈V-U中，找一條權(quán)值最小的邊(u,v)，并將v加入集合U中，邊(u,v)加入集合TE中。Prim算法步驟【例】對(duì)下面的圖G，使用普里姆算法求最小生成樹(shù)T的執(zhí)行過(guò)程。圖GPrim算法步驟Prim算法步驟Prim算法實(shí)現(xiàn)10頂點(diǎn)定義算法實(shí)現(xiàn)測(cè)試代碼頂點(diǎn)定義利用Prim算法來(lái)構(gòu)造最小生成樹(shù)，最終的生成樹(shù)由n個(gè)頂點(diǎn)以及n-1條邊組成。除了初始頂點(diǎn)外，由n-1次循環(huán)選取操作得到其余n-1個(gè)頂點(diǎn)和n-1條符合條件的邊，每次循環(huán)得到1個(gè)頂點(diǎn)和1條邊。Prim算法實(shí)現(xiàn)11頂點(diǎn)定義算法實(shí)現(xiàn)測(cè)試代碼算法實(shí)現(xiàn)lowCost數(shù)組，用來(lái)保存符合一個(gè)頂點(diǎn)在U，另外一個(gè)頂點(diǎn)在V-U中的邊的權(quán)值每次從lowCost數(shù)組中選取權(quán)值最小的邊修正lowCost中的值Prim算法實(shí)現(xiàn)12頂點(diǎn)定義算法實(shí)現(xiàn)測(cè)試代碼測(cè)試代碼Part03Kruskal算法Kruskal算法思想假設(shè)G=(V,E)是一個(gè)無(wú)向帶權(quán)圖，其中V是帶權(quán)圖中頂點(diǎn)的集合，E是邊的權(quán)值集合。最小生成樹(shù)為T(mén)=(V,TE)。重復(fù)步驟(2)直到所有頂點(diǎn)都在同一連通分量上為止。邊長(zhǎng)遞增的順序選擇E中的邊(u,v)加入到T中，要求u、v分屬于T的兩個(gè)連通分量；若u、v是T的當(dāng)前同一個(gè)連通分量中的頂點(diǎn)，則舍去此邊。初始化：T=(V,?)。也就是說(shuō)，最小生成樹(shù)的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖。Kruskal算法步驟【例】對(duì)下面的圖G，使用克魯斯卡爾算法求最小生成樹(shù)T