普里姆算法生成最小生成樹課程設(shè)計(完整版)
【正文】 向圖、無向圖及調(diào)用普里姆算法生成最小生成樹、流程圖繪制、任務(wù)書填寫由王彬彬完成；鄰接表存儲有向圖、無向圖及調(diào)用普里姆算法生成最小生成樹、菜單界面由周鑫完成；李松平、張圣瑋、魏遠迎主要負責文檔排版，代碼調(diào)試等綜合應(yīng)用。要完成一項任務(wù)或把東西學好就必須有足夠的信心，持久的耐心，有面對困難無所畏懼的精神，這對我日后的學習和生活產(chǎn)生了深遠的影響。不同的人會選擇不同的算法，所以即使同樣的程序，不同的人必然會設(shè)計出不同的方案，所以以后的學習生活中，一定要廣泛涉獵，掌握更多更好的解決問題的方法。 p=pnext。 else Medges[i][j]=MaxVertexNum。M=(graph*)malloc(sizeof(graph))。 i++) { printf([%d,%3d]=,i,gadjlist[i].vertex)。jGn。 for (i=0。 } printf(頂點的序號 =%d 邊的權(quán)值=%d\n,k,mincost)。i++) { mincost=max。 for(i=0。 sadjvex=i。j,amp。i++) {scanf(%d,amp。printf(\t==無向網(wǎng)圖鄰接表==\n)。 s=(edgenode*)malloc(sizeof(edgenode))。 gadjlist[i].firstedges=NULL。 scanf(%d,%d%*c,amp。 } printf(輸出頂點信息及鄰接矩陣:\n )。 for (k=0。(Gvexs[i]))。 printf(請輸入頂點數(shù)和邊數(shù)：)。weight)。j++){ if(i==j) Gedges[i][j]=0。 for (i=0。 }graph。typedef vertexnode AdjList[MaxVertexNum]。（2）鄰接表define MaxVertexNum 100typedef int vertextype。jGn。gadjlist[i].firstedges=s。k++)scanf(%d,%d,%d,amp。(ge))。第 6 頁 共 29 頁 for(j=0。k=1。 i=1。OutPut(G)。Y NGedges[i][j]=max。iGn。以下是兩個模塊的大體分析：1. 創(chuàng)建網(wǎng)圖并確定網(wǎng)圖的存儲形式，通過對題目要求的具體分析。最小生成樹輸出采用頂點集合和邊的集合的形式。從所有結(jié)點 u 屬于 U 和結(jié)點 v 屬于 V 但不屬于 U 的帶權(quán)邊中選出具有最小權(quán)值的邊（u，v） ，將結(jié)點 v 加入集合 U 中，將邊（u，v）加入集合 T 中。i++)for(j=0。j,amp。i++){ lowcost[i]=gm[0][i]。in。j++。edgenode *s。gadjlist[i].firstedges=NULL。sadjvex=j。for(i=0。 EdgeType edges[MaxVertexNum][MaxVertexNum]。typedef struct vnode{ vertextype vertex。typedef struct{ edgetype vexs[MaxVertexNum]。(Gn),amp。iGn。k++){ scanf(\n%d,%d,%d,amp。 prim(Gedges,Gn,Gvexs)。 for (i=0。j++){ if(i==j) Gedges[i][j]=0。weight)。 edgenode *s。ign。i,amp。 } DispAdjList(g)。 printf(\n 輸入頂點 :)。kge。 snext=gadjlist[i].firstedges。} 算法void prim(int gm[][MaxVertexNum ],int n,int closevertex[] ){ /*普里姆算法*/ int lowcost[100]。 closevertex[0]=0。lowcost[j]!=0) { mincost=lowcost[j]。 closevertex[j]=k。 for(i=0。第 19 頁 共 29 頁 printf(\n 網(wǎng)圖的鄰接表表示如下：\n)。 }}void change(ALgraph *g) /*鄰接表轉(zhuǎn)換成鄰接矩陣*/{ int i,j。i++) for(j=0。ign。第 28 頁 共 29 頁課程設(shè)計總結(jié)：本次課程設(shè)計涉及到的范圍雖不廣，但能夠比較系統(tǒng)的對 C 語言和數(shù)據(jù)結(jié)構(gòu)進行一次整理和復(fù)習。指導(dǎo)教師評語：指導(dǎo)教師(簽字)： 年 月 日課程
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1