信息工程大學算法設計與分析貪心法—最小生成樹國家級實驗教學示范中心計算機學科組規劃教材算法設計與分析Python案例詳解微課視頻版最小生成樹(Minimum-costSpanningTree)：設G=(V,E)是無向連通帶權圖，即一個網絡。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。

生成樹的性質：包含n個頂點；有且僅有(n-1)條邊；任兩點都是有路可達的。生成樹上各邊權的總和稱為該生成樹的耗費。耗費最小的生成樹稱為G的最小生成樹。1234566515366425

最小生成樹有廣泛應用。比如建立城市間的通信網絡、鄉村間的道路連通等問題，最小生成樹可以給出最優的建設方案。最小生成樹問題的本質：求無向連通帶權圖的最小連通代價。判斷題。對于一個無向連通帶權圖，最小生成樹可能是不唯一的。A.不正確B.正確Prim算法和Kruskal算法都是用貪心思想構造的最小生成樹。盡管它們的貪心策略不同，但都利用了最小生成樹性質。

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

1234566515366425123456112345614123456142123456154212345615342①②③④⑤⑥

需要的數據結構：標識頂點i是否屬于集合S：使用數組s如何有效地找出滿足條件i

S，j

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

對于V-S中每個頂點j，把S到j權值最小的點i存入parent[j]，權值c[i][j]存入dist[j]，當有新的點加入S時，更新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算法執行過程中相關數組的變化情況（parent[j]簡寫為p[j]，dist[j]簡寫為d[j]）1234561(1)5(4)3(5)4(2)2(3)voidprim(){/*prim算法構建最小生成樹*//*初始化*/s[1]=1;s[2~n]=0;forj=2ton ifc[1][j]!=INF{parent[j]=1;dist[j]=c[j][1]；}/*循環n-1次，依次加入點和邊*/for(k=1;k<=n-1;k++){/*找出V-S中dist值最小的頂點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中的點，判斷該邊權值是否更小，如果是，則修改parent和dist*/fori=2tonif(s[i]==0)&&dist[i]<c[j][i]){dist[i]=c[j][i];parent[i]=j;}}}時間復雜度：O(n2)最小生成樹性質：只要是連接兩個集合的權值最小的邊，一定在某棵最小生成樹中。Kruskal算法基本思想：1.

n個頂點看成n個孤立的連通分支，將所有的邊按權值從小到大排序；

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