普里姆算法生成最小生成樹(shù)_課程設(shè)計(jì)-資料下載頁(yè)
2025-08-16 20:15本頁(yè)面
【導(dǎo)讀】最小生成樹(shù)能夠選擇圖上的任意一點(diǎn)做根結(jié)點(diǎn)。樹(shù)輸出采用頂點(diǎn)集合和邊的集合的形式。根據(jù)課設(shè)題目要求，擬將整體程序分為兩大模塊。終點(diǎn)和權(quán)值）兩種存儲(chǔ)結(jié)構(gòu)，方便以后的編程。設(shè)置兩個(gè)新的集合U和T，其中U用于存放帶權(quán)圖G. 其思想是：令集合U的初值為U{u0}（即假設(shè)構(gòu)造最小生成。從所有結(jié)點(diǎn)u屬于U和。將結(jié)點(diǎn)v加入集合U中，將邊（u，v）加入集合T中。
【正文】 ) { printf([%d,%3d]=,i,gadjlist[i].vertex)。 p=gadjlist[i].firstedges。 while (p!=NULL) { printf((%d,%d),padjvex,pweight)。 p=pnext。 } printf(^\n)。 } } void change(ALgraph *g) /*鄰接表轉(zhuǎn)換成鄰接矩陣 */ { int i,j。 edgenode *p。 graph *M。 M=(graph*)malloc(sizeof(graph))。 Mn=gn。 Me=ge。 第 21 頁(yè) 共 29 頁(yè) for(i=0。iMe。i++) for(j=0。jMe。j++) if(i==j)Medges[i][j]=0。 else Medges[i][j]=MaxVertexNum。 for(i=0。ign。i++) Mvexs[i]=gadjlist[i].vertex。 for(i=0。ign。i++) { p=gadjlist[i].firstedges。 while(p) { Medges[i][padjvex]=pweight。 p=pnext。 } } prim(Medges,Mn,Mvexs)。 } 第 22 頁(yè) 共 29 頁(yè) 4 調(diào)試與分析 調(diào)試過(guò)程 測(cè)試數(shù)據(jù)（對(duì)下圖進(jìn)行測(cè)試）： 程序執(zhí)行過(guò)程 系統(tǒng)使用說(shuō)明： 1. 輸入的數(shù)據(jù)可以是 100 以內(nèi)的整數(shù)； 2. 本系統(tǒng)可以建立帶權(quán)圖，并能夠用 Prim 算法求該網(wǎng)圖的最小生成樹(shù)。 3. 該系統(tǒng)會(huì)有菜單提示，進(jìn)行選項(xiàng)： 右圖是 6 個(gè)頂點(diǎn)的 10 條邊的連通圖 六個(gè)頂點(diǎn)分別是： 1 2 3 4 5 6 頂點(diǎn)序號(hào)和邊上的權(quán)植分別是 0 1 11 0 2 15 0 3 18 1 2 33 1 4 12 2 3 20 2 4 22 2 5 25 3 5 27 4 5 29 1 2 4 3 5 6 第 23 頁(yè) 共 29 頁(yè) （ 1）有向圖鄰接矩陣輸出最小生成樹(shù) 截圖： 第 24 頁(yè) 共 29 頁(yè) （ 2）無(wú)向圖鄰接矩陣輸出最小生成樹(shù)截圖： 第 25 頁(yè) 共 29 頁(yè) 第 26 頁(yè) 共 29 頁(yè) （ 3） 有 向圖鄰接 表 輸出最小生成樹(shù)截圖： 第 27 頁(yè) 共 29 頁(yè) （ 4） 無(wú)向圖鄰接 表 輸出最小生成樹(shù)截圖： 第 28 頁(yè) 共 29 頁(yè) 參考文獻(xiàn) （ 1）李素若 ， 《數(shù)據(jù)結(jié)構(gòu)（ C 語(yǔ)言描述）》 ， 2020， 化學(xué)工業(yè)出版社 （ 2）嚴(yán)蔚敏 、 吳偉民 ， 《數(shù)據(jù)結(jié)構(gòu)（ C 語(yǔ)言描述）》 ， 1999， 清華大學(xué)出版社 （ 3） 徐孝凱 ， 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn) ， 2020， 清華大學(xué)出版社 （ 4） 孟佳娜 、 胡瀟琨 ， 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與習(xí)題 ， 2020， 機(jī)械工業(yè)出版社 附 錄 說(shuō)明： 本次課程設(shè)計(jì)由組長(zhǎng)周鑫，組員王彬彬、李松平、張圣瑋、魏遠(yuǎn)迎共同完成。其中鄰接矩陣存儲(chǔ)有向圖、無(wú)向圖及調(diào)用普里姆算法生成最小生成樹(shù)、流程圖繪制、任務(wù)書(shū)填寫(xiě)由王彬彬完成；鄰接表存儲(chǔ)有向圖、無(wú) 向圖及調(diào)用普里姆算法生成最小生成樹(shù)、菜單界面由周鑫完成；李松平、張圣瑋、魏遠(yuǎn)迎主要負(fù)責(zé)文檔排版，代碼調(diào)試等綜合應(yīng)用。 第 29 頁(yè) 共 29 頁(yè) 課程設(shè)計(jì)總結(jié)： 本次課程設(shè)計(jì)涉及到的范圍雖不廣，但能夠比較系統(tǒng)的對(duì) C 語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)進(jìn)行一次整理和復(fù)習(xí)。同時(shí)有了很多的體會(huì)和經(jīng)驗(yàn)。 1. 鞏固了以前學(xué)過(guò)的 C 語(yǔ)言的知識(shí)，在這次課程設(shè)計(jì)中我體會(huì)到 C 語(yǔ)言超強(qiáng)的邏輯性，能夠熟練使用 VC++的編譯環(huán)境，也對(duì)這兩門(mén)課程有了新的認(rèn)識(shí)，他們既有聯(lián)系，又相互區(qū)別，在編寫(xiě)程序過(guò)程中要靈活應(yīng)用 2. 對(duì)數(shù)據(jù)結(jié)構(gòu)的理解有待加強(qiáng)，算法的知識(shí)面也有待于提高。不同的人會(huì)選擇不同 的算法，所以即使同樣的程序，不同的人必然會(huì)設(shè)計(jì)出不同的方案，所以以后的學(xué)習(xí)生活中，一定要廣泛涉獵，掌握更多更好的解決問(wèn)題的方法。 3. 此次設(shè)計(jì)讓我意識(shí)到程序設(shè)計(jì)是腦力勞動(dòng)和體力勞動(dòng)相結(jié)合的，沒(méi)有平時(shí)基礎(chǔ)的訓(xùn)練是不會(huì)寫(xiě)出高效的算法。 4. 此次課程設(shè)計(jì)時(shí)間雖短， 課設(shè)的過(guò)程是短暫的，但我所收獲的是永恒的。它讓我嘗到了學(xué)習(xí)的快樂(lè)，成功的喜悅，更讓我懂得了不少做人的道理。要完成一項(xiàng)任務(wù)或把東西學(xué)好就必須有足夠的信心，持久的耐心，有面對(duì)困難無(wú)所畏懼的精神，這對(duì)我日后的學(xué)習(xí)和生活產(chǎn)生了深遠(yuǎn)的影響。 指導(dǎo)教師評(píng)語(yǔ)： 指導(dǎo)教師 (簽字 )： 年 月 日 課程設(shè)計(jì)成績(jī)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1