普里姆算法求最小生成樹課程設(shè)計報告(編輯修改稿)
2025-02-17 17:05 本頁面
【文章內(nèi)容簡介】 各條邊為:\n)。 for(i=1。i。i++)/**/ { k=MiniNum(closedge,G)。/*k為與U中頂點相鄰接的下一個頂點的序號*/ printf((%s%s)\n,closedge[k].adjvex,[k])。/*輸出生成樹的邊*/ closedge[k].lowcost=0。/*第k頂點并入U集*/ for(j=0。j。j++) if([k][j].adjclosedge[j].lowcost)/*新頂點加入U集后重新將最小邊存入到數(shù)組*/ { strcpy(closedge[j].adjvex,[k])。 closedge[j].lowcost=[k][j].adj。 } }}void OutPut (MGraph *G){ int i,j。 printf(\tE={ )。 for (i=0。iGn。i++) printf(%d ,Gvexs[i])。 printf(})。 printf(\n)。 for(i=0。iGn。i++) { for(j=0。jGn。j++) printf(\t%d ,Gedges[i][j])。 printf(\n)。 } }void DispAdjList(ALgraph *g) { int i。 edgenode *p。 printf(\n網(wǎng)圖的鄰接表表示如下：\n)。 for (i=0。 ign。 i++) { printf([%d,%3d]=,i,gadjlist[i].vertex)。 p=gadjlist[i].firstedges。 while (p!=NULL) { printf((%d,%d),padjvex,pweight)。 p=pnext。 } printf(^\n)。 }}void change(ALgraph *g) /*鄰接表轉(zhuǎn)換成鄰接矩陣*/{ int i,j。 edgenode *p。 graph *M。 M=(graph*)malloc(sizeof(graph))。 Mn=gn。 Me=ge。 for(i=0。iMe。i++) for(j=0。jMe。j++) if(i==j)Medges[i][j]=0。 else Medges[i][j]=MaxVertexNum。 for(i=0。ign。i++) Mvexs[i]=gadjlist[i].vertex。 for(i=0。ign。i++){ p=gadjlist[i].firstedges。 while(p) { Medges[i][padjvex]=pweight。 p=pnext。 } } prim(Medges,Mn,Mvexs)。}4 測試選取包含六個頂點及10條邊的圖進行程序的測試，分別將需要測試的數(shù)據(jù)按要求鍵入，根據(jù)提示進行下級菜單的確定與選擇，直到求解出測試數(shù)據(jù)的最小生成樹。 測試數(shù)據(jù) 測試數(shù)據(jù)圖（1）以有向圖鄰接矩陣的方式輸出最小生成樹（、）圖 圖 圖 （2） 以無向圖鄰接矩陣的方式輸出最小生成樹（、）圖 圖 （3） 以有向圖鄰接表的方式輸出最小生成樹（、）圖 圖 （4） 以無向圖鄰接表的方式輸出最小生成樹（、）圖 圖 5 總結(jié)說明：本次課程設(shè)計由周德、舒勝、黃義、樊坤共同完成。其中鄰接矩陣存儲有向圖、無向圖及調(diào)用普里姆算法生成最小生成樹、任務書填寫由舒勝、樊坤完成；鄰接表存儲有向圖、無向圖及調(diào)用普里姆算法生成最小生成樹、菜單界面由黃義完成；周德負責流程圖繪制、文檔排版等綜合應用。通過此次課程設(shè)計，我對圖的理解又上升了一個層次。數(shù)據(jù)結(jié)構(gòu)這門課是非常奧妙的。圖能夠在計算機中存在，首先要捕捉他有哪些具體化、數(shù)字化的信息，比如說權(quán)值、頂點個數(shù)等，這也就說明了想要把生活中的信息轉(zhuǎn)化到計算機中必須用數(shù)字來完整的構(gòu)成一個信息庫，而圖的存在，又涉及到了頂點之間的聯(lián)系。正是這些奇妙的東西引發(fā)我在計算機科學這條大路上一直迸發(fā)前進，勇敢的去探索科學中未知而美妙的事。參考文獻[1]（C語言描述）.2009，化學工業(yè)出版社. [2]嚴蔚敏,（C語言描述）.1999,清華大學出版社. [3]嚴蔚敏,(C語言版).1999，清華大學出版社.[4]嚴蔚敏,李冬梅,，清華大學出版社. [5](C語言描述).,電子工業(yè)出版社.附錄 全部代碼源程序：includeincludedefine MaxVertexNum 100define max 1000typedef int VertexType。typedef int EdgeType。typedef struct { VertexType vexs[MaxVertexNum]。 EdgeType edges[MaxVertexNum][MaxVertexNum]。 int n,e。 }MGraph。define MaxVertexNum 100typedef int vertextype。typedef struct node{ int adjvex。 int weight。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1