普里姆算法生成最小生成樹_課程設(shè)計(jì)

ID:4413539

大小:368.83 KB

頁(yè)數(shù):31頁(yè)

時(shí)間:2017-12-01

普里姆算法生成最小生成樹_課程設(shè)計(jì)_第1頁(yè)
普里姆算法生成最小生成樹_課程設(shè)計(jì)_第2頁(yè)
普里姆算法生成最小生成樹_課程設(shè)計(jì)_第3頁(yè)
普里姆算法生成最小生成樹_課程設(shè)計(jì)_第4頁(yè)
普里姆算法生成最小生成樹_課程設(shè)計(jì)_第5頁(yè)
資源描述:

《普里姆算法生成最小生成樹_課程設(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算法求該圖的最小生成樹。最小生成樹能夠選擇圖上的任意一點(diǎn)做根結(jié)點(diǎn)。最小生成樹輸出采用頂點(diǎn)集合和邊的集合的形式。1.2課程設(shè)計(jì)要求1.可以輸入頂點(diǎn)、邊數(shù)及各路徑的權(quán)值;2.通過(guò)建立無(wú)向圖或有向圖能過(guò)輸出鄰接矩陣或鄰接表;3.可以輸出建立的最小生成樹;4.畫出流程圖,且函數(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的最小生成樹的結(jié)點(diǎn)的集合,T用于存放帶權(quán)圖G的最小生成樹邊的權(quán)值的集合。其思想是:令集合U的初值為U{u0}(即假設(shè)構(gòu)造最小生成樹時(shí)從結(jié)點(diǎn)u0開始),集合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í),最小生成樹便構(gòu)造完畢。第28頁(yè)共29頁(yè)2.2原理圖介紹2.2.1功能模塊圖顯示菜單進(jìn)行選擇選擇創(chuàng)建(有)無(wú)向圖及存儲(chǔ)方式有向圖鄰接矩陣無(wú)向圖鄰

4、接矩陣有向圖鄰接表無(wú)向圖鄰接表調(diào)用普里姆算法輸出最小生成樹結(jié)束開始圖2.1功能模塊圖2.2.2流程圖分析1.主函數(shù)第28頁(yè)共29頁(yè)開始顯示菜單,選擇輸入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ù),輸出最小生成樹圖2.2主函數(shù)流程圖2.CreateMGraph()函數(shù)第28頁(yè)共29頁(yè)開始inti,j,kfor(i=0;in;i++)scanf(“%c”,&(G->vexs[i]));for(i=0;in;i++)for(

5、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ù)開始inti,j,k,lowcost[100],mincost;for(i=1;i

6、;}set[i]=0;i=1;j=1;YYlowcost[0]=0;closevertex[0]=0;for(i=1;i

7、流程圖第28頁(yè)共29頁(yè)4.createALgraph()函數(shù)開始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)

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。
关闭