裴現(xiàn)坤最小生成樹講解

1、離散數(shù)學最小生成樹問題姓名：裴現(xiàn)坤學 號：2013211613班級：計算機科學與技術13-1班實驗地點：實驗樓四號樓第三機房實驗時間：2014-12-31實驗目的和要求八口海上油井相互間距離如下表，其中 1號井離海岸最近，為5km。問從海 岸經(jīng)1號井鋪設油管把各井連接起來，怎樣連油管長度最短（為便于檢修，油管 只準在油井處分叉）？從到234567811.32.10.90.71.82.01.820.91.81.22.82.31.132.61.72.51.91.040.71.61.50.950.91.10.860.61.070.5目的運用最小生成樹思想和求最小生成樹程序解決實際問題2實驗環(huán)境和工具

2、C+語言環(huán)境實驗Deve c+ 5編譯器3實驗過程3.1程序思想1、將各個油井抽象化為圖的頂點，它們之間的距離為圖的權(quán)值2、用鄰接矩陣儲存圖的頂點和權(quán)值3、用一個輔助數(shù)組儲存未選進最小生成樹的邊和頂點4、主算法prim算法的圖解基本思想假設G= （V,巳是一個具有n個頂點的連通網(wǎng)，T=（U,TE）是G的最小 生成樹，其中U是T的頂點集，TE是T的邊集，U和TE的初值均為空集。 算法開始時，首先從V中任取一個頂點（假定取Vo），將它并入U中，此時 U=V，然后只要U是V的真子集，就從那些其一個端點已在T中，另一個端點仍在T外的所有邊中，找一條最短（即權(quán)值最?。┻?，假定為（i,j ）， 其中V U

3、,V （V-U）,并把該邊（i,j ）和頂點j分別并入T的邊集TE和頂 點集U,如此進行下去，每次往生成樹里并入一個頂點和一條邊，直到n-1次后就把所有n個頂點都并入到生成樹T的頂點集中，此時U=V TE中含有 n-1條邊，T就是最后得到的最小生成樹?？梢钥闯觯谄绽匪惴ㄖ?，是 采用逐步增加U中的頂點，常稱為“加點法”。為了實現(xiàn)這個算法在本設計 中需要設置一個輔助數(shù)組close，以記錄從U到V-U具有最小代價的邊。 當輔助數(shù)組中存在兩個或兩個以上的最小代價的邊時，此時最小生成樹的形態(tài)就不唯一，此時可以在程序中采用遞歸的算法思想求出每個最小生成樹。3.2程序核心代碼#i ncludestdio

4、.h#i ncludestri ng.h#i ncludemalloc.h#i ncludeiostream#include iomanipusing n amespace std;#defi ne MAX 10最多頂點個數(shù)#defi ne INFINIT 35768 表示極大值，即typedef structdouble adj; /adj 是權(quán)值類型ArcNode;typedef structint vexsMAX,vex nu m,arc num;/*vexs表示頂點向量;vexnum,arcnumf分別表示圖的頂點數(shù)和弧數(shù)*/ArcNode arcsMAXMAX;/* 鄰接矩陣 */A

5、djMatrix;typedef structint adjvex;/存放頂點編號double lowcost;/存放頂點權(quán)值Node;Node closeMAX;/求最小生成樹時的輔助數(shù)組/int flag=0;AdjMatrix *creat(AdjMatrix *G) / 創(chuàng)建無向網(wǎng)int i,j;double weight;G-vex num = 8;for(i=1;ivex nu m;i+)G-vexsi=i;for(i=1;ivex nu m;i+)for(j=i+1;jvex nu m;j+)cout weight;G-arcsij.adj=weight;G-arcsji.adj

6、=weight;return(G);int Minium(AdjMatrix *G ,Node close)/close中權(quán)值最小的邊int i,k;double mi n;min=INFINIT; 置最小權(quán)值為 INFINITfor(i=1;ivex nu m;i+)if(closei .lo wcostvexs n+=u;closek.lowcost=0;初始化 U=ufor(i=1;ivex nu m;i+)if(i!=k)對V-U中的頂點i,初始化closeiclosei.adjvex=u;closei .lo wcost=G-arcski.adj;/* closei是指未選中的邊 *

7、/for(j=1;jvexnum-1;j+)/找 n-1 條邊(n=G-vexnum)kO=Minium(G ,close);/closekO中存有當前最小邊(u0, v0)的信息 uO=closekO.adjvex;/uO U vO=G-vexskO; /vO V-U p-vexs n+=vO;將終點放入數(shù)組中s+=closekO.lowcost;求最小生成樹的權(quán)值之和cout(u0vO)tclosekO.lowcoste ndl;輸出最小生成樹的路徑closekO.lowcost=O;將頂點 vO 納入 U 集合for(i=1;ivexnum;i+) 在頂點 vO 并入 U 之后，更新 c

8、losedgeiif(G-arcskOi.adjarcskOi.adj; closei.adjvex=vO;coutvn最小生成樹中的頂點序列為：;for(i=O;ivex nu m;i+)cout vexsi;coutvve ndl;coutn最小生成樹的權(quán)值之和為：sendl;int ma in()/ 主函數(shù)int st;AdjMatrix *G ,*p;p=(AdjMatrix *)malloc(sizeof(AdjMatrix);cout *計算機科學與技術13-1裴現(xiàn)坤* *e ndl;coutsetw(46)普里姆最小生成樹算法!endl;coutn* *e ndl;G=creat

9、(p);st=1;coutendl利用普里姆算法從起點1號油井樹的路徑如下e ndle ndl;出發(fā)，最小生成coutn*“endl;cout 終點)權(quán)值e ndle ndl;prim(G,st);system(PAUSE);return 1;3.1輸入結(jié)果- 7 itt r JHl-Tm 一m二 二一 一m二J二二二 -JJJ ?J1 ?J1 ?JI J1 ?J1 一 - -宀一 - - 圭月青青青青圭星冃青青圭墾耳青主冃青青青 r、r r” pjt I319780898283167512001210112212123.1運行結(jié)果利用晉里姆算法從起點1號油井岀發(fā)最小生成樹的路徑如下K起點終點權(quán)值5 CS-46C8-320.70.7B.S0.5乩&0_9最小牛成樹中的頂點序列為： 1487&32 為km n 2 禾 -* 之“ 唇疋- 權(quán)M續(xù) 的第 S1 成油意 ttt 小短按 曰B甌請3.2運行結(jié)果分析根據(jù)最小生成樹路徑可以得出所需要的最短油管是10.2km,連接方式是按照1-5-4-8-7-6-3-2 的序列他們之間的距離是 5+0.7+0.7+0.8+0.5+0.6+1+0.9=10.2km