資源描述:
《【最新精選】普里姆算法生成最小生成樹_課程設計》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、JINGCHUUNIVERSITYOFTECHNOLOGY《數(shù)據(jù)結(jié)構(gòu)(C語言描述)》課程設計學院計算機工程學院班級12級軟件技術(shù)1班學號2012304040122、120124、133、121學生姓名周鑫、王彬彬、李松平張圣瑋、魏遠迎指導教師余云霞2014年1月3日目錄1課程設計介紹11.1課程設計內(nèi)容11.2課程設計要求12課程設計原理22.1課設題目粗略分析22.2原理圖介紹32.2.1功能模塊圖32.2.2流程圖分析33數(shù)據(jù)結(jié)構(gòu)分析103.1存儲結(jié)構(gòu)103.2算法描述124調(diào)試與分析224.1調(diào)試過程224.2程序執(zhí)行過程22參考文獻28附錄281課程
2、設計介紹1.1課程設計內(nèi)容編寫算法能夠建立帶權(quán)圖,并能夠用Prim算法求該圖的最小生成樹。最小生成樹能夠選擇圖上的任意一點做根結(jié)點。最小生成樹輸出采用頂點集合和邊的集合的形式。1.2課程設計要求1.可以輸入頂點、邊數(shù)及各路徑的權(quán)值;2.通過建立無向圖或有向圖能過輸出鄰接矩陣或鄰接表;3.可以輸出建立的最小生成樹;4.畫出流程圖,且函數(shù)有必要說明、注釋;5.課設完成后上交報告及核心代碼。第48頁共29頁2課程設計原理2.1課設題目粗略分析根據(jù)課設題目要求,擬將整體程序分為兩大模塊。以下是兩個模塊的大體分析:1.創(chuàng)建網(wǎng)圖并確定網(wǎng)圖的存儲形式,通過對題目要求的具體
3、分析。發(fā)現(xiàn)該題的主要操作是路徑的輸出,因此采用鄰接表和鄰接矩陣(起點、終點和權(quán)值)兩種存儲結(jié)構(gòu),方便以后的編程。2.Prim算法。設置兩個新的集合U和T,其中U用于存放帶權(quán)圖G的最小生成樹的結(jié)點的集合,T用于存放帶權(quán)圖G的最小生成樹邊的權(quán)值的集合。其思想是:令集合U的初值為U{u0}(即假設構(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)造完畢。第48頁共29頁2.2原理圖介
4、紹2.2.1功能模塊圖顯示菜單進行選擇選擇創(chuàng)建(有)無向圖及存儲方式有向圖鄰接矩陣無向圖鄰接矩陣有向圖鄰接表無向圖鄰接表調(diào)用普里姆算法輸出最小生成樹結(jié)束開始第48頁共29頁圖2.1功能模塊圖2.2.2流程圖分析1.主函數(shù)第48頁共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ù),輸出最小生成樹第48頁共29頁圖2.2主函數(shù)流程圖2.CreateMGraph()函數(shù)第48頁共29頁開始in
5、ti,j,kfor(i=0;in;i++)scanf(“%c”,&(G->vexs[i]));for(i=0;in;i++)for(j=0;in;i++)i=jG->edges[i][j]=0;YNG->edges[i][j]=max;for(k=0;ke;k++)scanf("%d,%d,%d",&i,&j,&weight);G->edges[i][j]=weight;OutPut(G);prim(G->edges,G->n,G->vexs);第48頁共29頁結(jié)束圖2.3CreateMGraph()函數(shù)流程圖第48頁
6、共29頁3.Prim()函數(shù)開始inti,j,k,lowcost[100],mincost;for(i=1;i
7、ncost);lowcost[k]=0;第48頁共29頁第48頁共29頁for(j=0;jn),&(g->e));for(i=0;in;i++)scanf("%d",&(g->adjlist[i].vertex));g->adjlist[i].fir
8、stedges=NULL;for(k=0;k