普里姆算法生成最小生成樹(shù)課程設(shè)計(jì)-wenkub.com
2025-06-24 10:19 本頁(yè)面
【正文】 要完成一項(xiàng)任務(wù)或把東西學(xué)好就必須有足夠的信心，持久的耐心，有面對(duì)困難無(wú)所畏懼的精神，這對(duì)我日后的學(xué)習(xí)和生活產(chǎn)生了深遠(yuǎn)的影響。不同的人會(huì)選擇不同的算法，所以即使同樣的程序，不同的人必然會(huì)設(shè)計(jì)出不同的方案，所以以后的學(xué)習(xí)生活中，一定要廣泛涉獵，掌握更多更好的解決問(wèn)題的方法。其中鄰接矩陣存儲(chǔ)有向圖、無(wú)向圖及調(diào)用普里姆算法生成最小生成樹(shù)、流程圖繪制、任務(wù)書(shū)填寫(xiě)由王彬彬完成；鄰接表存儲(chǔ)有向圖、無(wú)向圖及調(diào)用普里姆算法生成最小生成樹(shù)、菜單界面由周鑫完成；李松平、張圣瑋、魏遠(yuǎn)迎主要負(fù)責(zé)文檔排版，代碼調(diào)試等綜合應(yīng)用。 p=pnext。 for(i=0。 else Medges[i][j]=MaxVertexNum。iMe。M=(graph*)malloc(sizeof(graph))。 } printf(^\n)。 i++) { printf([%d,%3d]=,i,gadjlist[i].vertex)。 edgenode *p。jGn。 printf(\n)。 for (i=0。j++) if(gm[k][j]lowcost[j]) { lowcost[j]=gm[k][j]。 } printf(頂點(diǎn)的序號(hào) =%d 邊的權(quán)值=%d\n,k,mincost)。amp。i++) { mincost=max。 } lowcost[0]=0。 for(i=0。第 16 頁(yè) 共 29 頁(yè) } DispAdjList(g)。 sadjvex=i。 sweight=w。j,amp。 for(k=0。i++) {scanf(%d,amp。(ge))。printf(\t==無(wú)向網(wǎng)圖鄰接表==\n)。 gadjlist[i].firstedges=s。 s=(edgenode*)malloc(sizeof(edgenode))。k++) { scanf(%d,%d,%d,amp。 gadjlist[i].firstedges=NULL。 for(i=0。 scanf(%d,%d%*c,amp。} 3. 創(chuàng)建有向網(wǎng)圖鄰接表存儲(chǔ)void createAgraph( ALgraph *g) /*創(chuàng)建有向網(wǎng)圖*/{ int i,j,k,w。 } printf(輸出頂點(diǎn)信息及鄰接矩陣:\n )。j,amp。 for (k=0。jGn。(Gvexs[i]))。 printf(請(qǐng)輸入頂點(diǎn)信息:)。 printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：)。 printf(輸出最小生成樹(shù)的信息 :\n)。weight)。kGe。j++){ if(i==j) Gedges[i][j]=0。 for (i=0。 for (i=0。 scanf(%d,%d,amp。 }graph。(3)鄰接表轉(zhuǎn)換成鄰接矩陣輔助結(jié)構(gòu)體typedef int edgetype 。typedef vertexnode AdjList[MaxVertexNum]。 }edgenode。（2）鄰接表define MaxVertexNum 100typedef int vertextype。typedef struct { VertexType vexs[MaxVertexNum]。jGn。i++) printf(%d ,Gvexs[i])。gadjlist[i].firstedges=s。s=(edgenode*)malloc(sizeof(edgenode))。k++)scanf(%d,%d,%d,amp。(gadjlist[i].vertex))。(ge))。結(jié)束圖 Prim()函數(shù)流程圖第 7 頁(yè) 共 29 頁(yè)4. createALgraph()函數(shù)結(jié)束圖 createAgraph()函數(shù)流程圖開(kāi)始int i,j,k,w。第 6 頁(yè) 共 29 頁(yè) for(j=0。k=j。k=1。for(i=1。 i=1。in。OutPut(G)。i,amp。Y NGedges[i][j]=max。iGn。iGn。其思想是：令集合 U 的初值為 U{u0}（即假設(shè)構(gòu)造最小生成樹(shù)時(shí)從結(jié)點(diǎn) u0 開(kāi)始） ，集合 T 的初值為 T={}。以下是兩個(gè)模塊的大體分析：1. 創(chuàng)建網(wǎng)圖并確定網(wǎng)圖的存儲(chǔ)形式，通過(guò)對(duì)題目要求的具體分析。最小生成樹(shù)能夠選擇圖上的任意一點(diǎn)做根結(jié)點(diǎn)。最小生成樹(shù)輸出采用頂點(diǎn)集合和邊的集合的形式。發(fā)現(xiàn)該題的主要操作是路徑的輸出，因此采用鄰接表和鄰接矩陣（起點(diǎn)、終點(diǎn)和權(quán)值）兩種存儲(chǔ)結(jié)構(gòu)，方便以后的編程。從所有結(jié)點(diǎn) u 屬于 U 和結(jié)點(diǎn) v 屬于 V 但不屬于 U 的帶權(quán)邊中選出具有最小權(quán)值的邊（u，v） ，將結(jié)點(diǎn) v 加入集合 U 中，將邊（u，v）加入集合 T 中。i++)scanf(“\n%c”,amp。i++)f
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1