最小生成樹的Prim算法提高型實驗報告

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

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

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

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

5、ph ;函數(shù)設計/鄰接矩陣圖的當前頂點數(shù)和弧數(shù)/圖的種類標志函數(shù)名稱函數(shù)原型功能描述main() int main(void) 系統(tǒng)調用主函數(shù)Huiru() void Huitu () 繪制無向圖GraphicVer() void GraphicVer(Graph *G) 輸出鄰接矩陣 prim() void prim(Graph *G) PRIM 算法演示實驗源代碼#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 個頂點，n-1 條邊 */(lowcosti=G-edges1i;closesti = 1;lowcost1=0;/*標志頂點1加入U集合*/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;/*頂點 k 加入 U*/for(j=2;jv;j+)/*修改由頂點k到其他頂點邊的權值*/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 個頂點，n-1 條邊 */( lowcosti=G-edges1i;/* 初始化 */closesti = 1; /*頂點未加入到最小生成樹中*/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;/*頂點 k 加入 U*/drawwapicture(lowcost,closest,G-v);for(j=2;jv;j+)/*修改由頂點k到其他頂點邊的權值*/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;五.實驗結果分析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六.實驗小結通過此次實驗后我深刻地學習了最小生成樹的Prim算法，通過分析實驗目 的和實驗內容；闡述不同方法的原理；分析不同方法的特點和區(qū)別以及時空復雜 度；分析和調試測試數(shù)據(jù)和相應的結果.明白了 Prim算法是設計思想：設圖G = (V, E),其生成樹的頂點集合為U。把v0放入隊；在所有ueu, vey-U的邊 (u,v) eE中找一條最小權值的邊，加入生成樹；把找到的邊的v加入U集合。 如果U集合已有n個元素，則結束，否則繼續(xù)執(zhí)行。Prim算法實現(xiàn)：一方面 利用集合，設置一個數(shù)組set(i=0,1,.,n-1),初始值為0,代表對應