最小生成樹的Prim算法提高型實(shí)驗(yàn)報(bào)告

1、黃岡師范學(xué)院提高型實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課題最小生成樹的Prim算法（實(shí)驗(yàn)類型：口綜合性 設(shè)計(jì)性 應(yīng)用性）實(shí)驗(yàn)課程算法程序設(shè)計(jì)實(shí)驗(yàn)時(shí)間2010年12月24日學(xué)生姓名周媛鑫專業(yè)班級(jí)計(jì)科0801學(xué) 號(hào) 200826140110實(shí)驗(yàn)?zāi)康暮鸵蟾鶕?jù)算法設(shè)計(jì)需要，掌握連通網(wǎng)的靈活表示方法；掌握最小生成樹的Prim算法；熟練掌握貪心算法的設(shè)計(jì)方法；實(shí)驗(yàn)條件硬件環(huán)境：實(shí)驗(yàn)室電腦一臺(tái)軟件環(huán)境：winTC實(shí)驗(yàn)原理分析最小生成樹的定義：假設(shè)一個(gè)單位要在n個(gè)辦公地點(diǎn)之間建立通信網(wǎng)，則連通n個(gè)地點(diǎn)只需要n-1 條線路。可以用連通的無向網(wǎng)來表示n個(gè)地點(diǎn)以及它們之間可能設(shè)置的通信線路， 其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩地間的線路，賦

2、于邊的權(quán)值表示相應(yīng)的代價(jià)。 對于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以表示一 個(gè)通信網(wǎng)。其中一棵使總的耗費(fèi)最少，即邊的權(quán)值之和最小的生成樹，稱為最小 生成樹。構(gòu)造最小生成樹可以用多種算法。其中多數(shù)算法利用了最小生成樹的下面 一種簡稱為MST的性質(zhì)：假設(shè)N=(V,E)是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非 空子集。若(u,v)是一條具有最小權(quán)值(代價(jià))的邊，其中uU，veV-U，則必 存在一棵包含邊(u.v )的最小生成樹。普里姆(Prim)算法即是利用MST性質(zhì)構(gòu)造最小生成樹的算法。算法思想 如下：假設(shè)N=(V,E)和是連通網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U=u0(

3、u0 eV)，TE=(開始，重復(fù)執(zhí)行下述操作：在所有ueU，veV-U的邊(u, v) eE 中找一條代價(jià)最小的邊(u0, v0)并入集合TE，同時(shí)v0并入。，直到U=V為止。 此時(shí)TE中必有n-1條邊，則T=(V,TE)為N的最小生成樹。實(shí)驗(yàn)步驟數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：采用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)無向帶權(quán)圖更利于實(shí)現(xiàn)及操作：鄰接矩陣的抽象數(shù)據(jù)結(jié)構(gòu)定義：#define INFINITYINT_MAX/最大值#defineMAX_ERTEX_NUM20/最大頂點(diǎn)數(shù)typedef enum DG,DN,UDG,UDNGraphKind;/有向圖，有向網(wǎng)，無向網(wǎng)，無向圖 typedef struct Arc

4、 Cell(VRType adj ; / VRType是頂點(diǎn)關(guān)系的類型。對無權(quán)圖用1和0表示相鄰否；InfoType * info;/該弧相關(guān)信息的指針ArcCell ， AdjMatrix MAX_VERTEX_NUMMAX_VERTEX_NUM；Typedef struct (VertexType vexs MAX_VERTEX_NUM;頂點(diǎn)向量AdjMatrix arcs ; int vexnum , arcnum GraphKind kind ; Mgraph ;函數(shù)設(shè)計(jì)AdjMatrix arcs ; int vexnum , arcnum GraphKind kind ; Mgra

5、ph ;函數(shù)設(shè)計(jì)/鄰接矩陣圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)/圖的種類標(biāo)志函數(shù)名稱函數(shù)原型功能描述main() int main(void) 系統(tǒng)調(diào)用主函數(shù)Huiru() void Huitu () 繪制無向圖GraphicVer() void GraphicVer(Graph *G) 輸出鄰接矩陣 prim() void prim(Graph *G) PRIM 算法演示實(shí)驗(yàn)源代碼#include#include #include #include #include #define MaxVertexNum 50#define INF 32767typedef struct Graphic(char vex

6、sMaxVertexNum;int edgesMaxVertexNumMaxVertexNum;int v,e;Graph;char tmp10;void Huitu() /*無向圖的圖形生成*/(char buffer100;int graphdriver = DETECT, graphmode;int i,xbefore,ybefore;int x1,y1; char c;/*registerbgidriver(EGAVGA_driver);initgraph(&graphdriver, &graphmode, ); cleardevice();printf(input pot (300

7、x610,yv,&G-e);for(i=1;iv;i+)for(j=1;jv;j+)if(i=j) G-edgesij=0;else( G-edgesij=INF;for(k=1;ke;k+)printf(input %dth edge :,k);scanf(%d,%d,%d,&v1,&v2,&weight);G-edgesv1v2=G-edgesv2v1=weight;for(i=1;iv;i+)printf(n)；for(j=1;jv;j+)printf(G-edgesij=INF)?8t：dt，G-edgesij); printf(n)；system(pause)；/*prim 算法生成

8、最小生成樹*/void prim(Graph *G)(int lowcostMaxVertexNum,closestMaxVertexNum;int i,j,k,min;for(i=2;iv;i+)/*n 個(gè)頂點(diǎn)，n-1 條邊 */(lowcosti=G-edges1i;closesti = 1;lowcost1=0;/*標(biāo)志頂點(diǎn)1加入U(xiǎn)集合*/for(i=2;iv;i+)/*形成 n-1 條邊的生成樹 */(min=INF; k=0;for(j=2;jv;j+)if(lowcostjmin)&(lowcostj!=0)(min=lowcostj; k=j;printf(%d,%d)%2dt,

9、closestk,k,min);lowcostk=0;/*頂點(diǎn) k 加入 U*/for(j=2;jv;j+)/*修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值*/if(G-edgeskjedgeskj;closestj=k;printf(n)；void drawwapicture(int lowcost口，int closest口，int vex)( int i=0,x=0,datax=0;setviewport(150,140,630,310,1);cleardevice();setcolor(GREEN);rectangle(10,10,470,160);line(10,60,470,60);line(1

10、0,110,470,110);for(i=0;ivex;i+)(x=470-40*i;datax=470-20*i;line(x,10,x,160);if(vex-i)!=0)outtextxy(datax,35,(vex-i)0)；vsprintf(tmp,d，&lowcostvex-i);outtextxy(datax,85,tmp);vsprintf(tmp,d，&closestvex-i);outtextxy(datax,135,tmp);elseouttextxy(datax,35,i0)；outtextxy(datax,85,lowcost0)；outtextxy(datax,13

11、5,closest0);getche();closegraph();/*prim 算法生成最小生成樹*/void primyanshi(Graph *G)( void drawwapicture(int *p,int*q,int k);int lowcostMaxVertexNum,closestMaxVertexNum;int i,j,k,min;cleardevice();for(i=2;iv;i+)/*n 個(gè)頂點(diǎn)，n-1 條邊 */( lowcosti=G-edges1i;/* 初始化 */closesti = 1; /*頂點(diǎn)未加入到最小生成樹中*/drawwapicture(lowco

12、st,closest,G-v);lowcost1=0;drawwapicture(lowcost,closest,G-v);for(i=2;iv;i+)/*形成 n-1 條邊的生成樹 */(min=INF; k=0;for(j=2;jv;j+)if(lowcostjv);cprintf(%d,%d)%2dt，closestk,k,min);lowcostk=0;/*頂點(diǎn) k 加入 U*/drawwapicture(lowcost,closest,G-v);for(j=2;jv;j+)/*修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值*/if(G-edgeskjedgeskj;closestj=k;drawwa

13、picture(lowcost,closest,G-v);printf(n)；int main()(Graph *G=NULL;int flag=1;printf(/*/n)；printf(/*Welcome to the world of IRIS*/n);printf(/*200826140110*/n)；while(flag!=0)(printf(1:Build a Undigraph Net and output the adjMatrix.n)；printf(2.Output the Mini_tree:n)；printf(3.Display the procession of Mi

14、ni_tree with PRIM:n)；printf(4.exit:n)；scanf(%d,&flag);switch(flag)(printf(%d,flag);case 1:Huitu();GraphicVer(G);break;case 2:prim(G);break;case 3: primyanshi(G);break;default :printf(Thank you!n)；system(pause)；exit(0);printf(Thank you!n)；system(pause)； return 0;五.實(shí)驗(yàn)結(jié)果分析1th edjE：: 2li edljg- 3th巳的日：

15、1th edjE：: 2li edljg- 3th巳的日： 4th edge : 5th edge : JobTTTte datajwst pirtare nos in the cotruters memory.md ue reed hnu it pneimoy and ulietJier it ha雪 the correct data.33廿95 Q TOC o 1-5 h z 0西7B33廿95 Q45C16?eit03S G 95ITie 1th search to FinA tie min Yig砒 in the locust is the (1339Singnud i)ic iawi

16、rstCil-c IcsEstCU =0Zarrect Hie 1 aucDst? uiili Ihe sim 1 ier is-tance Letueen 4th dot and othen dots I hat is not be ffiqned.e 的 花。 i idn you cutcPi me 7六.實(shí)驗(yàn)小結(jié)通過此次實(shí)驗(yàn)后我深刻地學(xué)習(xí)了最小生成樹的Prim算法，通過分析實(shí)驗(yàn)?zāi)?的和實(shí)驗(yàn)內(nèi)容；闡述不同方法的原理；分析不同方法的特點(diǎn)和區(qū)別以及時(shí)空復(fù)雜 度；分析和調(diào)試測試數(shù)據(jù)和相應(yīng)的結(jié)果.明白了 Prim算法是設(shè)計(jì)思想：設(shè)圖G = (V, E),其生成樹的頂點(diǎn)集合為U。把v0放入隊(duì)；在所有ueu, vey-U的邊 (u,v) eE中找一條最小權(quán)值的邊，加入生成樹；把找到的邊的v加入U(xiǎn)集合。 如果U集合已有n個(gè)元素，則結(jié)束，否則繼續(xù)執(zhí)行。Prim算法實(shí)現(xiàn)：一方面 利用集合，設(shè)置一個(gè)數(shù)組set(i=0,1,.,n-1),初始值為0,代表對應(yīng)