普里姆算法生成最小生成樹課程設計

1、JINGCHU UNIVERSITY OF TECHNOLOGY數(shù)據(jù)結構（C語言描述）課程設計學院運算機工程學院班級12級軟件技術1班學 號 20、120124、133、121學生姓名周鑫、王彬彬、李松平張圣瑋、魏遠迎指導教師余云霞2014年1月3日1課程設計介紹.錯誤!未定義書簽。課程設計內(nèi)容錯誤!未定義書簽。課程設計要求錯誤!未定義書簽。2課程設計原理.課設題目粗略分析原理圖介紹功能模塊圖. 流程圖分析3數(shù)據(jù)結構分析.存儲結構算法描述錯誤!未定義書簽。錯誤!未定義書簽。 錯誤!未定義書簽。 錯誤!未定義書簽。 錯誤!未定義書簽。錯誤!未定義書簽。錯誤!未定義書簽。 錯誤!未定義書簽。4調(diào)試

2、與分析22調(diào)試進程22程序執(zhí)行進程22參考文獻28281課程設計介紹課程設計內(nèi)容編寫算法能夠成立帶權圖，并能夠用Prim算法求該圖的最小 生成樹。最小生成樹能夠選擇圖上的任意一點做根結點。最小生成 樹輸出采納極點集合和邊的集合的形式。課程設計要求1 .能夠輸入極點、邊數(shù)及各途徑的權值；2 .通過成立無向圖或有向圖能過輸出鄰接矩陣或鄰接表；3 .能夠輸出成立的最小生成樹；4 .畫出流程圖，且函數(shù)有必要說明、注釋；5 .課設完成后上交報告及核心代碼。2課程設計原理課設題目粗略分析依照課設題目要求，擬將整體程序分為兩大模塊。以下是兩個模塊 的大體分析：1.創(chuàng)建網(wǎng)圖并確信網(wǎng)圖的存儲形式，通過對題目要求

3、的具體分析。 發(fā)覺該題的要緊操作是途徑的輸出，因此采納鄰接表和鄰接矩陣（起點、 終點和權值）兩種存儲結構，方便以后的編程。算法。設置兩個新的集合U和T,其中U用于寄存帶權圖G的最小 生成樹的結點的集合，T用于寄存帶權圖G的最小生成樹邊的權值的集 合。其思想是：令集合U的初值為UuO（即假設構造最小生成樹時從 結點uO開始），集合T的初值為T=。從所有結點u屬于U和結點v 屬于V但不屬于U的帶權邊當選出具有最小權值的邊（u, v）,將結點v 加入集合U中，將邊（u, v）加入集合T中。如此不斷重復，當U=V時, 最小生成樹便構造完畢。原理圖介紹功能模塊圖圖功能模塊圖流程圖分析1.主函數(shù)圖主函數(shù)流

4、程圖2. CreateMGraph。函數(shù)開始圖CreateMGraph()函數(shù)流程圖3. Prim()函數(shù)圖Prim()函數(shù)流程圖4. create ALgraph()函數(shù)圖createAgraph。函數(shù)流程圖5.鄰接矩陣Output。輸出函數(shù)圖Output。函數(shù)流程圖3數(shù)據(jù)結構分析存儲結構概念鄰接矩陣及鄰接表的結構體(1)鄰接矩陣#define MaxVertexNum 100#define max 1000typedef int VertexType;typedef int EdgeType;typedef struct(VertexType vexsMaxVertexNum;EdgeTy

5、pe edgesMaxVertexNumMaxVertexNum;int n,e;JMGraph;(2)鄰接表#define MaxVertexNum 100 typedef int vertex type;typedef struct nodeint adj vex;int weight;struct node *next; edgenode;typedef struct vnode vertextype vertex;edgenode *firstedges; vertexnode;typedef vertexnode AdjListMaxVertexNum;typedef struct

6、Adj List adjlist;int n,e;JALgraph;(3)鄰接表轉換成鄰接矩陣輔助結構體typedef int edgetype;typedef struct(edgetype vexsMaxVertexNum;edgetype edgesMaxVertexNumMaxVertexNum;int n,e; graph;/*鄰接表轉換成鄰接矩陣輔助結構體*/算法描述1 .創(chuàng)建有向網(wǎng)圖鄰接矩陣存儲void CreateMGraph(MGraph *G)(int i,j,k,weight;printf(t=有向網(wǎng)圖鄰接矩陣=n“)；primf(”請輸入極點數(shù)和邊數(shù)：”)；scanf(

7、u%d,%du,&(G-n),&(G-e);printf(”請輸入極點信息:)；for (i=0;in;i+)scanf(n%dn,&(G-vexsi);for (i=0;in;i+)for (j=O;jn;j+) if(i=j) G-edgeSij=0;else G-edgesi j =max;/*初始化鄰接矩陣*/printf(輸入邊對應的兩個極點的序號及權值：”)；for (k=0;ke;k+)scanf(n%d,%d,%d&i,&j,&weight);G-edgesij=weight;printf(輸出極點信息及鄰接矩陣An”);OutPut(G);printf(“輸出最小生成樹的信息

8、:n) prim(G-edges,G-n,G-vexs);)2 .創(chuàng)建無向網(wǎng)圖鄰接矩陣存儲void CreateGraph(MGraph *G)(int ij,k,weight;printf(t=無向網(wǎng)圖鄰接矩陣=n)； printf(”請輸入極點數(shù)和邊數(shù)：);scanf(,%d,%d,&(G-n),&(G-e);printf(”請輸入極點信息:)；for (i=0;in;i+)scanf(n%du,&(G-vexsi);for (i=0;in;i+)for (j=O;jn;j+) if(i=j) G-edgesij=O;else G-edgesi j =max; /*初始化鄰接矩陣*/pri

9、ntf(輸入邊對應的兩個極點的序號及權值：);for (k=0;ke;k+) scanf(n%d,%d,%d,&i,&j,&weight);G-edgesij=weight;G-edgesji=weight;)printf(輸出極點信息及鄰接矩陣An);OutPut(G);printf(”輸出最小生成樹的信息An) prim(G-edges,G-n,G-vexs);)3 .創(chuàng)建有向網(wǎng)圖鄰接表存儲void createAgraph( ALgraph *g) /*創(chuàng)建有向網(wǎng)圖*/(int i,j,k,w;edgenode *s;printf(t=有向網(wǎng)圖鄰接表=n)printf(輸入極點數(shù)和邊數(shù)s

10、canf(%d,%d%*c,&(g-n),&(g-e);printf(n 輸入極點for(i=0;in;i+)scanf(u%d,&(g-adjlisti.vertex);g-adjlisti.firstedges=NULL;)printf(n輸入邊和權值:)；for(k=0;ke;k+)(scanf(%d,%d,%d,&i,&j,&w);s=(edgenode*)malloc(sizeof(edgenode);s-adjvex=j;s-weight=w;s-next=g-adjlisti.firstedges;g-adjlisti.firstedges=s;)DispAdjList(g);)

11、4 .創(chuàng)建無向網(wǎng)圖鄰接表存儲void createALgraph(ALgraph *g) /*創(chuàng)建無向網(wǎng)圖*/int i,j,k,w;edgenode *s;printf(t=E 向網(wǎng)圖鄰接表=n”);printf(輸入極點數(shù)和邊數(shù)scanf(%d,%d%*c,&(g-n),&(g-e);printf(n 輸入極點:)；for(i=0;in;i+)scanf(%d,&(g-adjlisti.vertex);g-adjlisti.firstedges=NULL;)printf(n輸入邊和權值:)；for(k=0;ke;k+)(scanf(u%d,%d,%d,&i,&j,&w);s=(edgeno

12、de*)malloc(sizeof(edgenode);s-adjvex=j;s-weight=w;s-next=g-adjlisti.firstedges;g-adjlisti.firstedges=s;s=(edgenode*)malloc(sizeof(edgenode);s-adjvex=i;s-weight=w;s-next=g-adj 1 ist j .firstedges;g-adj list j .firstedges=s;DispAdjList(g);算法void prim(int gmMaxVertexNum ,int njnt closevertex)/*普里姆算法*/i

13、nt lowcost100;int mincost;intfor(i=0;in;i+)(lowcosti=gm0i;closevertexi=0;)lowcost0=0;closevertex0=0;for(i=l;in;i+)(mincost=max;j=l；k=l； while(jn)(if(lowcostjmincost&lowcostj!=0)(mincost=lowcost j ;k寸)j+；)printf(極點的序號=%d邊的權值=%小門,1,mincost);lowcostk=0;for(j=0;jn;j+)if(gmkjlowcostj)(lowcostj=gmkj;close

14、vertexj=k;6 .輸出鄰接矩陣存儲函數(shù)void OutPut (MGraph *G)(int i,j;printf(MtE= n);for (i=0;in;i+)printf(M%d H,G-vexsi);printf(1,u)；printf(nM);for(i=0;in;i+)(for(j=0;jn;j+)printf(nt%d ,G-edgesij);printf(nH);)7 .輸出鄰接表存儲函數(shù)void DispAdjList(ALgraph *g)int i;edgenode *p;printf(n網(wǎng)圖的鄰接表表示如下：n);for (i=0; in; i+) printf(

15、,%d,%3d=,i,g-adjlisti.vertex);p=g-adjlist i .firstedges;while (p!=NULL)(printf(n(%d,%d)-,p-adjvex,p-weight);p=p-next;)printf(UAn);)8 .鄰接表轉換成鄰接矩陣函數(shù)void change(ALgraph *g)/*鄰接表轉換成令B接矩陣*/(int i,j;edgenode *p;graph *M;M=(graph*)malloc(sizeof(graph);M-n=g-n;M-e=g-e;for(i=0;ie;i+)for(j=0;je;j+)if(i=j)M-ed

16、gesij=O;else M-edgesij=MaxVertexNum;for(i=0;in;i+)M-vexsi=g-adjlisti.vertex;for(i=0;in;i+) p=g-adjlisti.firstedges;while(p)(M-edgesip-adjvex=p-weight;p=p-next;)prim(M-edges,M-n,M-vexs);4調(diào)試與分析調(diào)試進程測試數(shù)據(jù)（對以下圖進行測試）:右圖是6個頂點的10條邊的連通圖六個頂點分別是： 1 2 3 4 5 6頂點序號和邊上的權植分別是01110215031812331412232024222 5253 5274 5

17、29程序執(zhí)行進程系統(tǒng)利用說明：1 .輸入的數(shù)據(jù)能夠是100之內(nèi)的整數(shù)；2 .本系統(tǒng)能夠成立帶權圖，并能夠用Prim算法求該網(wǎng)圖的最小生成樹。3 .該系統(tǒng)會有菜單提示，進行選項:E:煤程設計Debugmai n .exe程程 過過 成成 生生圖圖 網(wǎng)網(wǎng) 有無 &二一&一 二 J 建建,H- 創(chuàng)5 - - - 12 3請選擇aw請選擇存儲方式,.4 .程序實際運行截圖（1）有向圖鄰接矩陣輸出最小生成樹截圖:E: 課程設計 De bu gm ain-exe1程程 過過 的一 nynv 成成 生生日嘉 及及 圖圖 網(wǎng)網(wǎng) ，向，向 有無B-二一&-I-TT 建建出包包一又一 *% TA12 3 =儲俄接

18、接收擇鄰鄰笨二2._一r ir0 G+ s_X予接。4的鄰；3點圖數(shù)2頂網(wǎng)邊:1個息兩-點點應頂人人邊151812332022 il,即M/s,3,4,2,3,4,52，5 ，2E:itSrtDebugma i n .exeM(ZE0.2.150.3.18L4.121.2.33上320br4.22b,5.253,5,27,529愉出頂點信息及鄰接矩陣;ie100010001000121000202225010002?1000e29100010000E= 12 3 45 601115100003310001000010001000100018001000100012 5 8 5 u 11112

19、n =i 疆rg收雙或con: 的的的的o半 隨邊邊邊邊邊yt法 05 14 2 3 5 e J 0月=一-二 klz? 18生號號號號號y輸 小序序序%一日 最的的的的的S橋 出點點點點點es狗 輸頂頂頂頂頂Fr搜（2）無向圖鄰接矩陣輸出最小生成樹截圖:11 E:課程窗十 De bugmain.exeH程程過過甘甘 成成 生生IX. / 日暨職 及及 圖圖 M網(wǎng) 洞無 E-一 l二一一 鹿建土創(chuàng)照 - - 12 3蕤髓儲1 .鄰2.鄰-適選擇存儲方式士“、七五回忸置鄰接矩陣= 卻夙入頂電毅型邊數(shù)： 鼓前幾頂點信息式2 3 4 5 6 俞人邊對應的兩，L2.151,3,18口，4/2p.3,2

20、0b,4.222,5.25卜5,27 限5,29.I觸狗拼音輸入法半：E;課程設計 Debugma in.exe0.2,150,3,18k421,2,333,20,明22,5,250.5,2?卜5 29怖出頂點信息及鄰接矩華15181000100033100012100002022252001000272210000295 6)E=C 1234153318100010001212 5 8 5 u 11112 n =i L值管值值值t叩=1 的的的的 o 半 隨邊邊邊邊邊yt法成=1=4=2=3=53人10生號號號號號 小序序 一取出點點點點點 俞頂頂頂頂頂（3）有向圖鄰接表輸出最小生成樹截圖:

21、XAUsersXxffADesktopXjEixFtXDebugXmain.exe，.創(chuàng)建有2.朝建光3 .退出句網(wǎng)同向圖及費;圖及矗=二*MX*,M*)W*X*W*K*,* *,= 請選擇：工諼避儲一，士請選擇存儲方式：2:有回忖圖鄰接表輸入頂點數(shù)和邊數(shù)二6。lm5 8 2 3 0 21113 2 24 2 3 4.Z才 ，3t11112 n 5 2 2 0 2 ?= = = = = i 112 2 2 2值值值值值 t f:2,4,02,2,h、“ fT -fr- *TTfr-1二二 o 攻3n n7?力力力力力 t 二、Ou 3- 5. ? 9 9 %TZ%T2 %T7 %T7 一刁 132222 y 乂， ， ， r r ，14235e 錄 3 2 5 5 5 4 = = = = = k a-x X X X X X OITO亍 OIPOITOIT y 接=序序序居an 新1 2 3 4 5 6燈燈燈內(nèi)的r JuiAf f A 口2.H1 s 的點點點點點es 圖田久山山質頂頂頂頂峰參考文獻（1）李素假設，數(shù)據(jù)結構（C語言描述），2020,化學工業(yè)出版社（2）嚴蔚敏、吳偉民，數(shù)據(jù)結