算法設計與分析 課件 第五章 貪心法 5.2.2 村村通最小成本問題

計算機算法設計與分析第5章貪心法5.2.2村村通最小成本問題村村通工程（通電、通水、通氣、通網(wǎng)、通路等）是中國政府推行的一個旨在改善農(nóng)村地區(qū)基礎設施和信息化水平的工程項目?，F(xiàn)某鄉(xiāng)鎮(zhèn)政府決定實現(xiàn)村村通公路，通過勘察已將各個村落之間的可修建道路成本數(shù)據(jù)統(tǒng)計在下表中，根據(jù)表中給出的數(shù)據(jù)，求使得每個村都有公路連通所需要的最低成本和具體修建線路。村落1111122345村落2345636456成本29845694635.2.2村村通最小成本問題用無向連通帶權圖G=（V，E）表示村落之間的道路數(shù)據(jù)及其公路修建成本，如圖所示，各個村落為圖G的頂點，村落之間有路連通用無向邊相連，邊的權值為修建村落公路的成本。村村通公路最小成本問題轉化為求圖G的最小生成樹問題。5.2.2村村通最小成本問題對一個無向連通帶權圖G，如果G的子圖G'是一棵包含G的所有頂點的樹，則稱G'為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。貪心策略1，Prim算法設圖G=（V,E）是無向連通帶權圖，V={1,2,...,n}

，E為邊集，cost[i][j]記錄頂點i到頂點j這條邊的權值。Prim算法構造最小生成樹的基本步驟如下：（1）置頂點集合S={1}；（2）只要S中頂點數(shù)目小于n，就作如下的貪心選擇：選取滿足條件i∈S，j∈V-S，且（i,j）邊權值cost[i][j]最小，將頂點j添加到S中。這個過程一直進行到|S|=|V|時為止，選取到的所有邊恰好構成G的一棵最小生成樹。貪心策略1，Prim算法1SSSSSSPrim算法正確性證明對于k<n，存在一棵最小生成樹包含Prim算法前k步選擇的邊。（1）首先證明k=1，存在一棵最小生成樹T包含邊e=（1，i），其中cost[1][i]是所有關聯(lián)頂點1的邊中權值最小的。Prim算法正確性證明設T是一棵最小生成樹，且T不包含邊（1，i），則T+（1，i）含有一條回路，刪除回路中關聯(lián)頂點1的另一條邊（1，j）得到一棵生成樹T'，如圖所示。因cost[1][i]≤cost[1][j]，所以生成樹T'的權值≤最小生成樹T的權值，與T是一棵最小生成樹矛盾。因此，與頂點1關聯(lián)的最小權值邊一定包含在一棵生成樹中。1ij

T1ij

1ij

T'Prim算法正確性證明（2）假設Prim算法第k步選擇的邊構成一棵最小生成樹的邊，證明算法第k+1步選擇的邊也構成一棵最小生成樹的邊。假設算法進行了k步，生成樹的邊為e1,e2,...,ek，這些邊的端點構成集合S，由歸納假設存在G的一棵最小生成樹T包含這些邊。算法第k+1步選擇頂點ik+1，則ik+1到S中頂點邊權值最小，設此邊ek+1=（ik，ik+1）。若ek+1∈T，則算法k+1顯然正確。Prim算法正確性證明若T不包含ek+1，將ek+1加T中形成一條回路，這條回路有另外一條連接S與頂點ik+1的邊e，令,則T*是一棵生成樹，包含e1,e2,...,ek，ek+1，且T*的各邊權值之和小于等于T的各邊權值之和，說明T*也是一顆最小生成樹，算法到k+1步仍然得到最小生成樹。證明過程如圖所示。權值最小ek+1i1ikS1

V-Sik+1e時間效率分析當使用鄰接矩陣存儲圖時，Prim算法的時間復雜度為O(n2)，其中n是頂點的數(shù)量。這是因為Prim算法需要遍歷每個頂點，并在每次迭代中找到與當前生成樹最近的頂點。當使用鄰接表存儲圖時，Prim算法的時間復雜