最小生成樹講解wOwz-pd.com最小生成樹引入:為一個(gè)鎮(zhèn)的9個(gè)村光纖鋪設(shè)做設(shè)計(jì)最小生成樹MSTMinimumSpannirngTree)樹任意兩個(gè)頂點(diǎn)間有且只有一條通路生成樹包括全部頂點(diǎn)且連通最小權(quán)值和最小最小生成樹的MST性質(zhì)及證明構(gòu)造最小生成樹有多種算法,其中多數(shù)算法用到了最小生成樹的下列種性質(zhì):假設(shè)N=(V,{E})是一個(gè)連通網(wǎng),U是頂點(diǎn)集V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值(代價(jià))的邊,其中u∈U,v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。證明:對(duì)于兩個(gè)點(diǎn)集,有最小的權(quán)值的邊(u,v),如果該圖的最小生成樹不包括這條邊的話,那么這棵樹就不是最小生成樹。我們假設(shè)任何一棵最小代價(jià)生成樹都不包含(u,v),由于樹都是連通圖,因而必定存在其他的邊聯(lián)通了頂點(diǎn)集U和VU,并且這樣的邊必須只有一條,否則便會(huì)形成回路,因?yàn)轫旤c(diǎn)集U和VU里面各個(gè)頂點(diǎn)也都是連通的。那么如果我們現(xiàn)在把輕邊(u,v)加入這個(gè)樹中,那么便形成回路了,那這個(gè)時(shí)候我們把原來(lái)的聯(lián)通U和VU的邊去掉,這樣形成的樹是比原來(lái)的那棵最小生成樹的代價(jià)還要小的,因?yàn)檫?u,v)是連接兩個(gè)點(diǎn)集之間的權(quán)值最小的邊。所以這棵新的樹才是最小生成樹,但是它包含了邊(u,v),所以與假設(shè)矛盾,結(jié)論成立。第一章最小生成樹算法第1普娜算法讓小大普里姆算法思想從連通網(wǎng)N={V,B中的某一頂點(diǎn)U出發(fā),選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(U,v),將其頂點(diǎn)加入到生成樹的頂點(diǎn)集合U中。2、以后每一步從一個(gè)頂點(diǎn)在U中,而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到集合U中。3、如此繼續(xù)下去,直到網(wǎng)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。簡(jiǎn)單證明prim算法反證法:假設(shè)prim生成的不是最小生成樹1).設(shè)prim生成的樹為G02).假設(shè)存在Gmin使得cost(Gmin)<cost(G0)則在Gmin中存在<u,v>不屬于G0·3).將<u,>加入G0中可得一個(gè)環(huán),且<u,v>不是該環(huán)的最長(zhǎng)邊(這是因?yàn)?lt;u,v>∈Gmin)4).這與prim每次生成最短邊矛盾●5).故假設(shè)不成立,命題得證普里姆算法過(guò)程演示110+20+12+8+16+19+7+16=最小生成樹權(quán)值Prim算法實(shí)例起點(diǎn){v2,v3,vlowcost5v}4,y5,v6}3advelowcost056y)2.,5,v6}6adivexIvl,V3lowcost1v2v3v4y5v6w(v2,v4y5}4v0615∞∞aaivex3Iv1,v3.v6053lowcost150564adver50IVI,V3,Vv5}5∞36∞0606,v4,v24260djivIv3.v6,v4,v2,v}9普里姆最小生成樹算法與dijkstra最短路徑算法相同:l:同一種貪心策略,從VU中選最小權(quán)值點(diǎn)加入U(xiǎn)中不同1:應(yīng)用prim所有連通和最小dijkstraA到其他最