普里姆算法生成最小生成樹課程設(shè)計-文庫吧
2025-06-12 10:19 本頁面
【正文】 可以輸出建立的最小生成樹；4. 畫出流程圖，且函數(shù)有必要說明、注釋；5. 課設(shè)完成后上交報告及核心代碼。第 1 頁 共 29 頁2 課程設(shè)計原理 課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，擬將整體程序分為兩大模塊。以下是兩個模塊的大體分析：1. 創(chuàng)建網(wǎng)圖并確定網(wǎng)圖的存儲形式，通過對題目要求的具體分析。發(fā)現(xiàn)該題的主要操作是路徑的輸出，因此采用鄰接表和鄰接矩陣（起點、終點和權(quán)值）兩種存儲結(jié)構(gòu)，方便以后的編程。 算法。設(shè)置兩個新的集合 U 和 T，其中 U 用于存放帶權(quán)圖 G的最小生成樹的結(jié)點的集合，T 用于存放帶權(quán)圖 G 的最小生成樹邊的權(quán)值的集合。其思想是：令集合 U 的初值為 U{u0}（即假設(shè)構(gòu)造最小生成樹時從結(jié)點 u0 開始） ，集合 T 的初值為 T={}。從所有結(jié)點 u 屬于 U 和結(jié)點 v 屬于 V 但不屬于 U 的帶權(quán)邊中選出具有最小權(quán)值的邊（u，v） ，將結(jié)點 v 加入集合 U 中，將邊（u，v）加入集合 T 中。如此不斷重復，當 U=V 時，最小生成樹便構(gòu)造完畢。第 2 頁 共 29 頁 原理圖介紹 功能模塊圖顯示菜單進行選擇選擇創(chuàng)建（有）無向圖及存儲方式有向圖鄰接矩陣 無向圖鄰接矩陣 有向圖鄰接表 無向圖鄰接表調(diào)用普里姆算法輸出最小生成樹結(jié)束開始圖 功能模塊圖 流程圖分析1. 主函數(shù)第 3 頁 共 29 頁開始顯示菜單，選擇輸入 1 或 2選擇 1 選擇 2 調(diào)用 createAgraph()函數(shù)結(jié)束選擇 1調(diào)用 CreateGraph()函數(shù)選擇 2調(diào)用 CreateMGraph()函數(shù)調(diào)用 createALgraph()函數(shù)調(diào)用 Prim 函數(shù)，輸出最小生成樹 圖 主函數(shù)流程圖2. CreateMGraph()函數(shù)第 4 頁 共 29 頁開始int i,j,kfor(i=0。iGn。i++)scanf(“\n%c”,amp。(Gvexs[i]))。for(i=0。iGn。i++)for(j=0。iGn。i++)i=jGedges[i][j]=0。Y NGedges[i][j]=max。for (k=0。kGe。k++)scanf(\n%d,%d,%d,amp。i,amp。j,amp。weight)。Gedges[i][j]=weight。OutPut(G)。prim(Gedges,Gn,Gvexs)。 圖 CreateMGraph()函數(shù)流程圖結(jié)束第 5 頁 共 29 頁3．Prim()函數(shù)開始int i,j,k,lowcost[100],mincost。for(i=1。in。i++){ lowcost[i]=gm[0][i]。closevertex[i]=0。 }set[i]=0。 i=1。 j=1。YYlowcost[0]=0。closevertex[0]=0。for(i=1。in。i++)mincost=max。j=1。k=1。jnlowcost[j]mincostamp。amp。lowcost[j]!=0mincost=lowcost[j]。k=j。j++。NNprintf(頂點的序號=%d 邊的權(quán)值=%d\n,k,mincost)。 lowcost[k]=0。第 6 頁 共 29 頁 for(j=0。jn。j++)gm[k][j]lowcost[j]lowcost[j]=gm[k][j]。 closevertex[j]=k。結(jié)束圖 Prim()函數(shù)流程圖第 7 頁 共 29 頁4. createALgraph()函數(shù)結(jié)束圖 createAgraph()函數(shù)流程圖開始int i,j,k,w。edgenode *s。scanf(%d,%d%*c,amp。(gn),amp。(ge))。for(i=0。ign。i++)scanf(%d,amp。(gadjlist[i].vertex))。gadjlist[i].firstedges=NULL。for(k=0。kge。k++)scanf(%d,%d,%d,amp。i,amp。j,amp。w)。s=(edgenode*)malloc(sizeof(edgenode))。sadjvex=j。sweight=w。snext=gadjlist[i].firstedges。gadjlist[i].firstedges=s。第 8 頁 共 29 頁5. 鄰接矩陣 Output()輸出函數(shù)開始int i,j。for (i=0。iGn。i++) printf(%d ,Gvexs[i])。for(i=0。iGn。i++)for(j=0。jGn。j++)printf(\t%d ,Gedges[i][j])。結(jié)束圖 Output()函數(shù)流程圖
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1