算法設(shè)計(jì)與分析 課件 第五章 貪心法 5.2.2 村村通最小成本問題

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

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

T1ij

1ij

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

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