算法設(shè)計與分析第8講 貪心方法-MST.ppt

《算法設(shè)計與分析第8講 貪心方法-MST.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、貪心方法1最小生成樹問題有向圖G=(V,E),V是頂點集合，E是有向邊集合，

2、E

3、=O(V2)=>lg

4、E

5、=θ(lgV)圖的表示1）鄰接矩陣表示,G=(V,E),V=(1,2,…n)如果邊(i,j)∈E,A[i,j]=1，否則A[i,j]=0.空間存儲=V2,格式是稀疏的，如果圖是鏈表或者樹。213422鏈接表表示方法Adj(1)={2,3}Adj(2)={3}Adj(3)={}Adj(4)={3}

6、Adj(v)

7、=度（無向圖），出度（有向圖）?？臻g占用＝θ(V)+θ(2E)3最小生成樹(MST)Input:無向帶權(quán)連通圖，G=(V,E),w:E->R,

8、假設(shè)所有的權(quán)值不同。Output:一生成樹T,連接所有的頂點，具有最小的權(quán)值和W(T)=∑(u,v)∈TW(u,v)612515971081434最優(yōu)子結(jié)構(gòu)特點假設(shè)上圖是一棵最小生成樹T，刪除一條邊e，則成為兩課樹(T1,T2)，而每一棵都是一個最小生產(chǎn)子樹。否則，假設(shè)T1’是一個比T1更小的生成樹,則（T1’+e+T2）是比T更小的生成樹。故最優(yōu)子結(jié)構(gòu)特點成立。T1T2e5重疊子結(jié)構(gòu)特點按最優(yōu)子結(jié)構(gòu)性質(zhì)，可把節(jié)點集合V分成任意兩個子集（v1,V-v1）(v2,V-v2),…然后分別求最優(yōu)生成樹(T1,T1’),(T2,T2’),…再分別合并成t1,t2,

9、…。T應(yīng)該是其中最小的一棵。在求T1最小生成樹時，會繼續(xù)打斷,生成T11,T12.T2打斷時，會生成T21,T22,但T21＝T11是可能的，故重疊子結(jié)構(gòu)成立t1t2e6貪心方法既有最優(yōu)子結(jié)構(gòu)，又有重疊子結(jié)構(gòu)，可以用動態(tài)規(guī)劃。但本講使用更強(qiáng)大的方法－貪心法貪心方法的標(biāo)志：貪心選擇特性－某個局部最優(yōu)選擇，是全局最優(yōu)的。定理：T是G=(V,E)的最小生成樹，令A(yù)是V的子集，假如(u,v)∈E是連結(jié)A和V-A的最小邊，則(u,v)∈T.7上圖是最小生成樹，其中紅點集合為A,蘭點集合為V-A.假設(shè)(u,v)邊權(quán)值是目前權(quán)最小連結(jié)A和V-A的邊卻不在生成樹中。通過M

10、ST,找到一條u到v的路徑，找到碰到的第一個連結(jié)A和V-A的邊，打斷它，把(u,v)加入，還是一個生成樹。因為（u.v）更短，故新的樹權(quán)和更小。從而原樹為MST矛盾.uv8MST的prim算法思路：令V-A為一優(yōu)先隊列Q，每個Q的元素記錄優(yōu)先值的key為到A的最小權(quán)值Q=V,key(V)=∞,key(s)=0//s任意WhileQ!=NULLu=Extract_min(Q)foreachv∈Adj(u)ifv∈Q&&w(u,v)

11、雜性Time=θ(V+Vtextract+Etdeckey)Q用不同的結(jié)構(gòu)，時間有所區(qū)別textracttdeckeyTime數(shù)組θ(v)θ(1)θ(V2)最小堆θ(lgv)θ(lgv)θ(Elgv)Fib堆θ(lgv)θ(1)θ(E+Vlgv)10