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