算法設(shè)計(jì)與分析 課件 6.6-貪心法應(yīng)用-最小生成樹(shù)

信息工程大學(xué)算法設(shè)計(jì)與分析貪心法—最小生成樹(shù)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版最小生成樹(shù)(Minimum-costSpanningTree)：設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱(chēng)G’為G的生成樹(shù)。

生成樹(shù)的性質(zhì)：包含n個(gè)頂點(diǎn)；有且僅有(n-1)條邊；任兩點(diǎn)都是有路可達(dá)的。生成樹(shù)上各邊權(quán)的總和稱(chēng)為該生成樹(shù)的耗費(fèi)。耗費(fèi)最小的生成樹(shù)稱(chēng)為G的最小生成樹(shù)。1234566515366425

最小生成樹(shù)有廣泛應(yīng)用。比如建立城市間的通信網(wǎng)絡(luò)、鄉(xiāng)村間的道路連通等問(wèn)題，最小生成樹(shù)可以給出最優(yōu)的建設(shè)方案。最小生成樹(shù)問(wèn)題的本質(zhì)：求無(wú)向連通帶權(quán)圖的最小連通代價(jià)。判斷題。對(duì)于一個(gè)無(wú)向連通帶權(quán)圖，最小生成樹(shù)可能是不唯一的。A.不正確B.正確Prim算法和Kruskal算法都是用貪心思想構(gòu)造的最小生成樹(shù)。盡管它們的貪心策略不同，但都利用了最小生成樹(shù)性質(zhì)。

uv頂點(diǎn)集U頂點(diǎn)集V-UMST性質(zhì)證明：（反證法）假設(shè)G的任何一棵最小生成樹(shù)中都不包含邊(u,v)。設(shè)T是G的一棵最小生成樹(shù)，但不包含邊(u,v)。由于T是樹(shù)，且是連通的，因此必有一條從u到v的路徑，且該路徑上必有一條連接兩個(gè)頂點(diǎn)集U和V-U的邊(u',v')，其中u'屬于U，v'屬于V-U。將邊(u,v)加入到T中，得到一個(gè)含邊(u,v)的回路。當(dāng)刪除邊(u',v')時(shí)，回路被消除。由此得到另一棵生成樹(shù)T’，T’和T的區(qū)別僅在于用邊(u,v)取代了T中的邊(u’,v’)。因?yàn)?u,v)的權(quán)<=(u’,v’)的權(quán)，故T‘的權(quán)值<=T的權(quán)值。因此，T’也是G的最小生成樹(shù)，并包含邊（u,v），與假設(shè)矛盾。uu'vv'頂點(diǎn)集U頂點(diǎn)集V-U

1234566515366425123456112345614123456142123456154212345615342①②③④⑤⑥

需要的數(shù)據(jù)結(jié)構(gòu)：標(biāo)識(shí)頂點(diǎn)i是否屬于集合S：使用數(shù)組s如何有效地找出滿足條件i

S，j

V-S，且權(quán)值c[i][j]最小的邊(i,j)？

對(duì)于V-S中每個(gè)頂點(diǎn)j，把S到j(luò)權(quán)值最小的點(diǎn)i存入parent[j]，權(quán)值c[i][j]存入dist[j]，當(dāng)有新的點(diǎn)加入S時(shí)，更新parent[j]和dist[j]。1234566515366425迭代Sjp[2]d[2]p[3]d[3]p[4]d[4]p[5]d[5]p[6]d[6]初始{1}161115—∞—∞1{1,3}335111536342{1,3,6}635116236343{1,3,6,4}435116236344{1,3,6,4,2}235116223345{1,3,6,4,2,5}3511622334Prim算法執(zhí)行過(guò)程中相關(guān)數(shù)組的變化情況（parent[j]簡(jiǎn)寫(xiě)為p[j]，dist[j]簡(jiǎn)寫(xiě)為d[j]）1234561(1)5(4)3(5)4(2)2(3)voidprim(){/*prim算法構(gòu)建最小生成樹(shù)*//*初始化*/s[1]=1;s[2~n]=0;forj=2ton ifc[1][j]!=INF{parent[j]=1;dist[j]=c[j][1]；}/*循環(huán)n-1次，依次加入點(diǎn)和邊*/for(k=1;k<=n-1;k++){/*找出V-S中dist值最小的頂點(diǎn)j*/inttmin=INF;j=-1;fori=2ton if(s[i]==0)&&dist[i]<tmin){tmin=dist[i];j=i;}s[j]=1;/*將j添加到S中*//*依次判斷和j相鄰且在V-S中的點(diǎn)，判斷該邊權(quán)值是否更小，如果是，則修改parent和dist*/fori=2tonif(s[i]==0)&&dist[i]<c[j][i]){dist[i]=c[j][i];parent[i]=j;}}}時(shí)間復(fù)雜度：O(n2)最小生成樹(shù)性質(zhì)：只要是連接兩個(gè)集合的權(quán)值最小的邊，一定在某棵最小生成樹(shù)中。Kruskal算法基本思想：1.

n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支，將所有的邊按權(quán)值從小到大排序；

2.依次查看每一條邊(i,j)，如果i和j分別來(lái)自不同的連通分支T1和T2時(shí)，就用邊(i,j)將T1和T2連接成一個(gè)連通分支；3.重復(fù)步驟2，直到只剩下一個(gè)連通分支時(shí)為止。1234561212345611234561534212345612312345665153664251234561423①②③④⑤⑥Kruskal算法中的關(guān)鍵步驟：邊按權(quán)值從小到大排序逐一判斷邊的兩個(gè)鄰接點(diǎn)是否在同一個(gè)連通分支中，如不是1）合并兩個(gè)端點(diǎn)所在的分支2）把邊加入最小生成樹(shù)中用并查集高效