第4章第6節(jié) 最小生成樹(shù)(C++版)

1、第六節(jié)第六節(jié) 最小生成樹(shù)最小生成樹(shù)引入 一、什么是圖的最小生成樹(shù)（MST）？ 不知道大家還記不記得樹(shù)的一個(gè)定理：N個(gè)點(diǎn)用N-1條邊連接成一個(gè)連通塊，形成的圖形只可能是樹(shù)，沒(méi)有別的可能。一個(gè)有N個(gè)點(diǎn)的圖，邊一定是大于等于N-1條的。圖的最小生成樹(shù)，就是在這些邊中選擇N-1條出來(lái)，連接所有的N個(gè)點(diǎn)。這N-1條邊的邊權(quán)之和是所有方案中最小的。引入二、最小生成樹(shù)用來(lái)解決什么問(wèn)題？就是用來(lái)解決如何用最小的“代價(jià)”用N-1條邊連接N個(gè)點(diǎn)的問(wèn)題。例如：【例4-9】、城市公交網(wǎng)建設(shè)問(wèn)題【問(wèn)題描述】有一張城市地圖，圖中的頂點(diǎn)為城市，無(wú)向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)為在這兩個(gè)城市之間修建高速公路的造價(jià)，研

2、究后發(fā)現(xiàn)，這個(gè)地圖有一個(gè)特點(diǎn)，即任一對(duì)城市都是連通的?，F(xiàn)在的問(wèn)題是，要修建若干高速公路把所有城市聯(lián)系起來(lái)，問(wèn)如何設(shè)計(jì)可使得工程的總造價(jià)最少？【輸入格式】 n（城市數(shù)，1=n=100）e（邊數(shù)）以下e行，每行3個(gè)數(shù)i,j,wij，表示在城市i,j之間修建高速公路的造價(jià)?！据敵龈袷健縩-1行，每行為兩個(gè)城市的序號(hào)，表明這兩個(gè)城市間建一條高速公路。引入【輸入樣例】5 81 2 22 5 95 4 74 1 101 3 124 3 65 3 32 3 8【輸出樣例】1 22 33 43 5Prim算法 Prim算法采用與Dijkstra、Bellman-Ford算法一樣的“藍(lán)白點(diǎn)”思想：白點(diǎn)代表已經(jīng)進(jìn)

3、入最小生成樹(shù)的點(diǎn)，藍(lán)點(diǎn)代表未進(jìn)入最小生成樹(shù)的點(diǎn)。算法描述：以1為起點(diǎn)生成最小生成樹(shù)，minv表示藍(lán)點(diǎn)v與白點(diǎn)相連的最小邊權(quán)。MST表示最小生成樹(shù)的權(quán)值之和。a）初始化：minv= (v1); min1=0;MST=0;b）for (i = 1; i= n; i+)1.尋找minu最小的藍(lán)點(diǎn)u。2.將u標(biāo)記為白點(diǎn)3.MST+=minu4.for 與白點(diǎn)u相連的所有藍(lán)點(diǎn)v if (wuvminv) minv=wuv;c）算法結(jié)束： MST即為最小生成樹(shù)的權(quán)值之和算法分析&思想講解： Prim算法每次循環(huán)都將一個(gè)藍(lán)點(diǎn)u變?yōu)榘c(diǎn)，并且此藍(lán)點(diǎn)u與白點(diǎn)相連的最小邊權(quán)minu還是當(dāng)前所有藍(lán)點(diǎn)中最小的

4、。這樣相當(dāng)于向生成樹(shù)中添加了n-1次最小的邊，最后得到的一定是最小生成樹(shù)。我們通過(guò)對(duì)下圖最小生成樹(shù)的求解模擬來(lái)理解上面的思想。藍(lán)點(diǎn)和虛線代表未進(jìn)入最小生成樹(shù)的點(diǎn)、邊；白點(diǎn)和實(shí)線代表已進(jìn)入最小生成樹(shù)的點(diǎn)、邊。Prim算法 初始時(shí)所有點(diǎn)都是藍(lán)點(diǎn)，min1=0,min2、3、4、5=。權(quán)值之和MST=0。123452471162第一次循環(huán)自然是找到min1=0最小的藍(lán)點(diǎn)1。將1變?yōu)榘c(diǎn)，接著枚舉與1相連的所有藍(lán)點(diǎn)2、3、4，修改它們與白點(diǎn)相連的最小邊權(quán)。123452471162min2=w12=2;min3=w13=4;min4=w14=7;Prim算法 第二次循環(huán)是找到min2最小的藍(lán)點(diǎn)2。將2變

5、為白點(diǎn)，接著枚舉與2相連的所有藍(lán)點(diǎn)3、5，修改它們與白點(diǎn)相連的最小邊權(quán)。123452471162min3=w23=1;min5=w25=2;第三次循環(huán)是找到min3最小的藍(lán)點(diǎn)3。將3變?yōu)榘c(diǎn)，接著枚舉與3相連的所有藍(lán)點(diǎn)4、5，修改它們與白點(diǎn)相連的最小邊權(quán)。123452471162min4=w34=1;由于min5=2 w35=6;所以不修改min5的值。Prim算法 最后兩輪循環(huán)將點(diǎn)4、5以及邊w25,w34添加進(jìn)最小生成樹(shù)。123452471162最后權(quán)值之和MST=6。 這n次循環(huán)，每次循環(huán)我們都能讓一個(gè)新的點(diǎn)加入生成樹(shù)，n次循環(huán)就能把所有點(diǎn)囊括到其中；每次循環(huán)我們都能讓一條新的邊加入生成

6、樹(shù)，n-1次循環(huán)就能生成一棵含有n個(gè)點(diǎn)的樹(shù)；每次循環(huán)我們都取一條最小的邊加入生成樹(shù)，n-1次循環(huán)結(jié)束后，我們得到的就是一棵最小的生成樹(shù)。這就是Prim采取貪心法生成一棵最小生成樹(shù)的原理。算法時(shí)間復(fù)雜度：O (N2)。Prim算法 【例4-10】、最優(yōu)布線問(wèn)題(wire.cpp)【問(wèn)題描述】學(xué)校有n臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來(lái)。兩臺(tái)計(jì)算機(jī)被連接是指它們間有數(shù)據(jù)線連接。由于計(jì)算機(jī)所處的位置不同，因此不同的兩臺(tái)計(jì)算機(jī)的連接費(fèi)用往往是不同的。 當(dāng)然，如果將任意兩臺(tái)計(jì)算機(jī)都用數(shù)據(jù)線連接，費(fèi)用將是相當(dāng)龐大的。為了節(jié)省費(fèi)用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺(tái)計(jì)算機(jī)可以間接的通過(guò)若干

7、臺(tái)計(jì)算機(jī)（作為中轉(zhuǎn)）來(lái)實(shí)現(xiàn)與另一臺(tái)計(jì)算機(jī)的連接?，F(xiàn)在由你負(fù)責(zé)連接這些計(jì)算機(jī)，任務(wù)是使任意兩臺(tái)計(jì)算機(jī)都連通（不管是直接的或間接的）?！据斎敫袷健枯斎胛募ire.in，第一行為整數(shù)n（2=n=100），表示計(jì)算機(jī)的數(shù)目。此后的n行，每行n個(gè)整數(shù)。第x+1行y列的整數(shù)表示直接連接第x臺(tái)計(jì)算機(jī)和第y臺(tái)計(jì)算機(jī)的費(fèi)用?！据敵龈袷健枯敵鑫募ire.out，一個(gè)整數(shù)，表示最小的連接費(fèi)用?！据斎霕永?0 1 21 0 12 1 0【輸出樣例】 2 （注：表示連接1和2，2和3，費(fèi)用為2）Prim算法 【參考程序】/wire#include#include#includeusing namespace st

8、d;int g101101; /鄰接矩陣int minn101; /minni存放藍(lán)點(diǎn)i與白點(diǎn)相連的最小邊權(quán)bool u101; /ui=True，表示頂點(diǎn)i還未加入到生成樹(shù)中 /ui=False，表示頂點(diǎn)i已加入到生成樹(shù)中 int n,i,j;int main() freopen(wire.in,r,stdin); freopen(wire.out,w,stdout); cin n; for (i = 1; i = n; i+) for (j = 1; j gij; memset(minn,0 x7f,sizeof(minn); /初始化為maxint minn1 = 0; memset(u

9、,1,sizeof(u); /初始化為True，表示所有頂點(diǎn)為藍(lán)點(diǎn)Prim算法 for (i = 1; i = n; i+) int k = 0; for (j = 1; j = n; j+) /找一個(gè)與白點(diǎn)相連的權(quán)值最小的藍(lán)點(diǎn)k if (uj & (minnj minnk) k = j; uk = false; /藍(lán)點(diǎn)k加入生成樹(shù)，標(biāo)記為白點(diǎn) for (j = 1; j = n; j+) /修改與k相連的所有藍(lán)點(diǎn) if (uj & (gkj minnj) minnj = gkj; int total = 0; for (i = 1; i = n; i+) /累加權(quán)值 tota

10、l += minni; cout total endl; return 0;Kruskal算法 Kruskal（克魯斯卡爾）算法是一種巧妙利用并查集來(lái)求最小生成樹(shù)的算法。首先我們把無(wú)向圖中相互連通的一些點(diǎn)稱為處于同一個(gè)連通塊中。例如下圖 圖中有3個(gè)連通塊。1、2處于一個(gè)連通塊中，4、5、6也處于一個(gè)連通塊中，孤立點(diǎn)3也稱為一個(gè)連通塊。Kruskal算法將一個(gè)連通塊當(dāng)做一個(gè)集合。Kruskal首先將所有的邊按從小到大順序排序（一般使用快排），并認(rèn)為每一個(gè)點(diǎn)都是孤立的，分屬于n個(gè)獨(dú)立的集合。然后按順序枚舉每一條邊。如果這條邊連接著兩個(gè)不同的集合，那么就把這條邊加入最小生成樹(shù)，這兩個(gè)不同的集合就合并

11、成了一個(gè)集合；如果這條邊連接的兩個(gè)點(diǎn)屬于同一集合，就跳過(guò)。直到選取了n-1條邊為止。123456Kruskal算法 算法描述:初始化并查集。fatherx=x。tot=0將所有邊用快排從小到大排序。計(jì)數(shù)器 k=0;for (i=1; i=M; i+) /循環(huán)所有已從小到大排序的邊 if 這是一條u,v不屬于同一集合的邊(u,v)(因?yàn)橐呀?jīng)排序，所以必為最小)， begin 合并u,v所在的集合，相當(dāng)于把邊(u,v)加入最小生成樹(shù)。 tot=tot+W(u,v) k+ 如果k=n-1,說(shuō)明最小生成樹(shù)已經(jīng)生成，則break; end;1.6. 結(jié)束，tot即為最小生成樹(shù)的總權(quán)值之和。Kruskal

12、算法 思想講解：Kruskal（克魯斯卡爾）算法開(kāi)始時(shí)，認(rèn)為每一個(gè)點(diǎn)都是孤立的，分屬于n個(gè)獨(dú)立的集合。1234521289673105個(gè)集合 1，2，3，4，5 生成樹(shù)中沒(méi)有邊Kruskal每次都選擇一條最小的邊，而且這條邊的兩個(gè)頂點(diǎn)分屬于兩個(gè)不同的集合。將選取的這條邊加入最小生成樹(shù)，并且合并集合。Kruskal算法 第一次選擇的是這條邊，將這條邊加入到生成樹(shù)中，并且將它的兩個(gè)頂點(diǎn)1、2合并成一個(gè)集合。1234521289673104個(gè)集合 1，2，3，4，5 生成樹(shù)中有一條邊 第二次選擇的是這條邊，將這條邊加入到生成樹(shù)中，并且將它的兩個(gè)頂點(diǎn)4、5合并成一個(gè)集合。123452128967310

13、3個(gè)集合 1，2，3，4，5 生成樹(shù)中有2條邊 ，Kruskal算法 第三次選擇的是這條邊，將這條邊加入到生成樹(shù)中，并且將它的兩個(gè)頂點(diǎn)3、5所在的兩個(gè)集合合并成一個(gè)集合1234521289673102個(gè)集合 1，2，3，4，5 生成樹(shù)中有3條邊 ，第四次選擇的是這條邊，將這條邊加入到生成樹(shù)中，并且將它的兩個(gè)頂點(diǎn)2、5所在的兩個(gè)集合合并成一個(gè)集合。1234521289673101個(gè)集合 1，2，3，4，5 生成樹(shù)中有4條邊 ，Kruskal算法 算法結(jié)束，最小生成樹(shù)權(quán)值為19。通過(guò)上面的模擬能夠看到，Kruskal算法每次都選擇一條最小的，且能合并兩個(gè)不同集合的邊，一張n個(gè)點(diǎn)的圖總共選取n-1次

14、邊。因?yàn)槊看挝覀冞x的都是最小的邊，所以最后的生成樹(shù)一定是最小生成樹(shù)。每次我們選的邊都能夠合并兩個(gè)集合，最后n個(gè)點(diǎn)一定會(huì)合并成一個(gè)集合。通過(guò)這樣的貪心策略，Kruskal算法就能得到一棵有n-1條邊，連接著n個(gè)點(diǎn)的最小生成樹(shù)。Kruskal算法的時(shí)間復(fù)雜度為O(E*logE)，E為邊數(shù)。Kruskal算法 【例4-11】、最短網(wǎng)絡(luò)Agri-Net【問(wèn)題描述】農(nóng)民約翰被選為他們鎮(zhèn)的鎮(zhèn)長(zhǎng)！他其中一個(gè)競(jìng)選承諾就是在鎮(zhèn)上建立起互聯(lián)網(wǎng)，并連接到所有的農(nóng)場(chǎng)。當(dāng)然，他需要你的幫助。約翰已經(jīng)給他的農(nóng)場(chǎng)安排了一條高速的網(wǎng)絡(luò)線路，他想把這條線路共享給其他農(nóng)場(chǎng)。為了用最小的消費(fèi)，他想鋪設(shè)最短的光纖去連接所有的農(nóng)場(chǎng)。你

15、將得到一份各農(nóng)場(chǎng)之間連接費(fèi)用的列表，你必須找出能連接所有農(nóng)場(chǎng)并所用光纖最短的方案。每?jī)蓚€(gè)農(nóng)場(chǎng)間的距離不會(huì)超過(guò)100000?！据斎敫袷健俊据敵龈袷健?只有一個(gè)輸出，其中包含連接到每個(gè)農(nóng)場(chǎng)的光纖的最小長(zhǎng)度?！据斎霕永縜grinet.in 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0【輸出樣例】agrinet.out28Kruskal算法 【參考程序】/agrinet#include#include#include /sort()需要用到庫(kù)using namespace std;struct point int x; int y; int v; ; /定義結(jié)構(gòu)類型

16、，表示邊point a9901; /存邊int fat101;int n,i,j,x,m,tot,k;int father(int x) if (fatx != x) fatx = father(fatx); return fatx; void unionn(int x,int y) int fa = father(x); int fb = father(y); if (fa != fb) fatfa = fb; Kruskal算法 int cmp(const point &a,const point &b) /sort()自定義的比較函數(shù) if (a.v n; for (i

17、= 1; i = n; i+) for (j = 1; j x; if (x != 0) m+; am.x = i; am.y = j; am.v = x; for (i = 1; i = n; i+) fati = i;sort(a+1,a+m+1,cmp); /C+標(biāo)準(zhǔn)庫(kù)中自帶的快排 /cmp為自定義的比較函數(shù)。表示a數(shù)組的1-m按規(guī)則cmp排序Kruskal算法 for (i = 1; i = m; i+) if (father(ai.x) != father(ai.y) unionn(ai.x,ai.y); tot += ai.v; k+; if (k = n-1) break; co

18、ut tot; return 0;上機(jī)練習(xí) 1、局域網(wǎng)【問(wèn)題描述】某個(gè)局域網(wǎng)內(nèi)有n(n=100)臺(tái)計(jì)算機(jī)，由于搭建局域網(wǎng)時(shí)工作人員的疏忽，現(xiàn)在局域網(wǎng)內(nèi)的連接形成了回路，我們知道如果局域網(wǎng)形成回路那么數(shù)據(jù)將不停的在回路內(nèi)傳輸，造成網(wǎng)絡(luò)卡的現(xiàn)象。因?yàn)檫B接計(jì)算機(jī)的網(wǎng)線本身不同，所以有一些連線不是很暢通，我們用f(i,j)表示i,j之間連接的暢通程度(f(i,j)=1000)，f(i,j)值越小表示i,j之間連接越通暢，f(i,j)為0表示i,j之間無(wú)網(wǎng)線連接。現(xiàn)在我們需要解決回路問(wèn)題，我們將除去一些連線，使得網(wǎng)絡(luò)中沒(méi)有回路，并且被除去網(wǎng)線的f(i,j)最大，請(qǐng)求出這個(gè)最大值?！据斎敫袷健康谝恍袃蓚€(gè)正整數(shù)n k接下來(lái)的k行每行三個(gè)正整數(shù)i j m表示i,j兩臺(tái)計(jì)算機(jī)之間有網(wǎng)線聯(lián)通，通暢程度為m?！据?/p>