北京信息科技大學(xué)軟件課程設(shè)計(jì)

1、北京信息科技大學(xué)計(jì)算機(jī)軟件基礎(chǔ)課程設(shè)計(jì)題 目： 最小生成樹最優(yōu)通信網(wǎng) 學(xué) 院： 信息與通信工程學(xué)院 專 業(yè)： 通信工程專業(yè) 學(xué)生姓名： XXXX 班級(jí)/學(xué)號(hào) 通信14XX/2014XXXXX 指導(dǎo)老師： 李振松，曹林 起止時(shí)間： 9月24日 至 10月30日 摘要題目6最小生成樹最優(yōu)通信網(wǎng)（難度系數(shù)10，全部做出給100分）主要內(nèi)容1、 如果以無(wú)向圖表示n個(gè)城市之間的通信網(wǎng)絡(luò)的建設(shè)規(guī)劃，頂點(diǎn)表示城市，邊上權(quán)值表示該線路的造價(jià)，設(shè)計(jì)一個(gè)方案，使這個(gè)通信網(wǎng)的總造價(jià)最低。2、 學(xué)會(huì)建立圖的鄰接表，理解圖的基本概念。3、 學(xué)會(huì)編寫DLL函數(shù)。4、 掌握建立最小生成樹的Prim算法、Kruskal算法。

2、5、 掌握C+編程環(huán)境的基本調(diào)試方法，熟練使用可視化C+編程工具。6、 提示：在每?jī)蓚€(gè)城市之間都可以設(shè)置一條線路，相應(yīng)地都要付出一定的經(jīng)濟(jì)代價(jià)。n個(gè)城市之間，最多可能設(shè)置n(n-1)/2條線路，那么，如何在這些可能的線路中選擇n-1條，使總的耗費(fèi)最少，構(gòu)成最優(yōu)通信網(wǎng)呢？這個(gè)問題本質(zhì)上就是構(gòu)造連通圖的最小代價(jià)生成樹。設(shè)計(jì)要求1、上交課程設(shè)計(jì)的書面材料，要求打印。包括課程設(shè)計(jì)任務(wù)書、主要內(nèi)容，源程序，對(duì)程序的功能進(jìn)行客觀評(píng)價(jià)，明確指出自己編寫了哪些具體函數(shù)。2、上交電子版源程序，包括鄰接表建立程序、Prim算法、Kruskal算法。3、自己編寫一個(gè)求素?cái)?shù)函數(shù)，把它書寫成一個(gè)動(dòng)態(tài)鏈接庫(kù)形式，并在主函

3、數(shù)中調(diào)用它。嘗試把自己編寫的程序?qū)懗蓜?dòng)態(tài)鏈接庫(kù)和靜態(tài)鏈接庫(kù)形式（無(wú)需上交），并比較以下三種EXE文件的大小。A：調(diào)用靜態(tài)鏈接庫(kù)生成的EXE執(zhí)行文件。B：調(diào)用動(dòng)態(tài)鏈接庫(kù)生成的EXE執(zhí)行文件。C：直接調(diào)用函數(shù)生成的EXE執(zhí)行文件。主要儀器設(shè)備計(jì)算機(jī)一臺(tái)，安裝Windows XP 操作系統(tǒng)、Microsoft Visual C+ 6.0、MSDN Library。主要參考文獻(xiàn)1 侯俊杰. 深入淺出MFC(第二版)M. 武漢：華中科技大學(xué)出版社, 2001.2 譚浩強(qiáng). C程序設(shè)計(jì)（第二版）M. 北京：清華大學(xué)出版社, 1999.3 孟彩霞. 計(jì)算機(jī)軟件基礎(chǔ)M. 陜西：西安電子科技大學(xué)出版社, 200

4、3.4 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)M. 北京：清華大學(xué)出版社, 2005.課程設(shè)計(jì)進(jìn)度計(jì)劃（起止時(shí)間、工作內(nèi)容）選做圖的遍歷和最小生成樹題目的同學(xué)，2人1組，1人做圖的遍歷，1人做最小生成樹，整個(gè)課程設(shè)計(jì)共20學(xué)時(shí)，具體進(jìn)度如下：4 學(xué)時(shí) 了解課題背景，選題，學(xué)習(xí)DLL，學(xué)習(xí)圖的基本概念。4 學(xué)時(shí) 編寫鄰接表建立程序。4 學(xué)時(shí) 最小生成樹Prim算法。4 學(xué)時(shí) 最小生成樹Kruskal算法。4 學(xué)時(shí) 調(diào)試程序，答辯。課程設(shè)計(jì)開始日期見選題說明課程設(shè)計(jì)完成日期見選題說明課程設(shè)計(jì)實(shí)驗(yàn)室名稱計(jì)算中心機(jī)房地 點(diǎn)健翔橋校區(qū)摘要 最小生成樹最優(yōu)通信網(wǎng)對(duì)于這個(gè)題目，首先，我想到的是如何來(lái)構(gòu)建一個(gè)通信網(wǎng)，也

5、就是如何構(gòu)建一張無(wú)向圖，當(dāng)然圖在計(jì)算機(jī)內(nèi)的存儲(chǔ)有 很多種，我這里應(yīng)用了鄰接表來(lái)存儲(chǔ)無(wú)向圖，但是后來(lái)又將其轉(zhuǎn)換成鄰接矩陣和邊集數(shù)組的形式來(lái)存儲(chǔ)，一方面我想了解比對(duì)一下這幾種存儲(chǔ)方式，另一方面也使得接下來(lái)的prim算法和Kruskal算法的處理變得容易，再 說一下這兩個(gè)最小生成樹的算法，prim算法相比較而言更適合較多節(jié)點(diǎn) 的圖，而Kruskal算法則更適合于較少節(jié)點(diǎn)的圖，prim算法給我的感覺更像是順藤摸瓜，它先有一個(gè)起始點(diǎn)，之后順著這個(gè)點(diǎn)往下遍歷，當(dāng)找到最優(yōu)路徑時(shí)，我的想法是就把他們合為一個(gè)整體，依次將整個(gè)圖的最優(yōu)路徑遍歷出來(lái)，而Kruskal算法我感覺稍稍有一點(diǎn)不足，就是需要對(duì)權(quán)值進(jìn)行排序，

6、這在很多節(jié)點(diǎn)時(shí)就顯得很不足，但這個(gè)算法對(duì)于節(jié)點(diǎn)很少的圖來(lái)說非常好，基本上結(jié)果就是那個(gè)排好序的邊集數(shù)組的前幾項(xiàng)，當(dāng)然如果形成環(huán)，就再加幾項(xiàng)，我想這種情況也不是特別特別常見，因此很多時(shí)候不需要完整遍歷整個(gè)圖，所以相對(duì)較好一些，最后說一下輸出，我這里采用鄰接表和鏈接矩陣兩種方式來(lái)做輸出。19參考文獻(xiàn)目錄 任務(wù)書1摘要2目錄3正文4參考文獻(xiàn)11源代碼12int main()函數(shù)用途：主函數(shù)是這個(gè)工程的入口函數(shù)，函數(shù)調(diào)用菜單函數(shù)，開始整個(gè)程序的運(yùn)行void menu();函數(shù)用途：菜單函數(shù)，詢問用戶接下來(lái)要做的事情，并調(diào)用響應(yīng)的功能函數(shù)void addHeadNode();函數(shù)用途：添加頭節(jié)點(diǎn)void

7、addNode();函數(shù)用途：添加普通節(jié)點(diǎn)void change();函數(shù)用途：將鄰接表轉(zhuǎn)換成鄰接矩陣void completeNode();函數(shù)用途：完成輸入，輸出當(dāng)前的鄰接表和鄰接矩陣void MiniSpanTree_Prim();函數(shù)用途：prim算法計(jì)算輸出最優(yōu)路徑int Find(int *parent,int f);函數(shù)用途：Kruskal算法判斷是否構(gòu)成環(huán)路void MiniSpanTree_Kruskal();函數(shù)用途：Kruskal算法計(jì)算輸出最優(yōu)路徑以下為概念部分，即在學(xué)習(xí)過程中參考的一些概念或者別人的理解圖的鄰接矩陣存儲(chǔ)方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈?zhǔn)?/p>

8、分配相結(jié)合的存儲(chǔ)結(jié)構(gòu)。如這個(gè)表頭結(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)存在相鄰頂點(diǎn)，則把相鄰頂點(diǎn)依次存放于表頭結(jié)點(diǎn)所指向的單向鏈表中。表結(jié)點(diǎn)存放的是鄰接頂點(diǎn)在數(shù)組中的索引。對(duì)于無(wú)向圖來(lái)說，使用鄰接表進(jìn)行存儲(chǔ)也會(huì)出現(xiàn)數(shù)據(jù)冗余，表頭結(jié)點(diǎn)A所指鏈表中存在一個(gè)指向C的表結(jié)點(diǎn)的同時(shí)，表頭結(jié)點(diǎn)C所指鏈表也會(huì)存在一個(gè)指向A的表結(jié)點(diǎn)。鄰接表是圖的一種最主要存儲(chǔ)結(jié)構(gòu),用來(lái)描述圖上的每一個(gè)點(diǎn)。對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)容器(n個(gè)頂點(diǎn)建立n個(gè)容器)，第i個(gè)容器中的結(jié)點(diǎn)包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。實(shí)際上我們常用的鄰接矩陣就是一種未離散化每個(gè)點(diǎn)的邊集的鄰接表。在有向圖中，描述每個(gè)點(diǎn)向別的節(jié)點(diǎn)連的邊(點(diǎn)a-點(diǎn)b這種情況)。在無(wú)向圖中，描述每個(gè)點(diǎn)所

9、有的邊(點(diǎn)a-點(diǎn)b這種情況)與鄰接表相對(duì)應(yīng)的存圖方式叫做邊集表，這種方法用一個(gè)容器存儲(chǔ)所有的邊。普里姆算法（Prim算法），圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點(diǎn)（英語(yǔ)：Vertex (graph theory)），且其所有邊的權(quán)值之和亦為最小。該算法于1930年由捷克數(shù)學(xué)家沃伊捷赫亞爾尼克（英語(yǔ)：Vojtch Jarnk）發(fā)現(xiàn)；并在1957年由美國(guó)計(jì)算機(jī)科學(xué)家羅伯特普里姆（英語(yǔ)：Robert C. Prim）獨(dú)立發(fā)現(xiàn)；1959年，艾茲格迪科斯徹再次發(fā)現(xiàn)了該算法。1).輸入：一個(gè)加權(quán)連通圖，其中頂點(diǎn)集合為V，邊集合

10、為E；2).初始化：Vnew= x，其中x為集合V中的任一節(jié)點(diǎn)（起始點(diǎn)），Enew= ,為空；3).重復(fù)下列操作，直到Vnew= V：a.在集合E中選取權(quán)值最小的邊，其中u為集合Vnew中的元素，而v不在Vnew集合當(dāng)中，并且vV（如果存在有多條滿足前述條件即具有相同權(quán)值的邊，則可任意選取其中之一）；b.將v加入集合Vnew中，將邊加入集合Enew中；4).輸出：使用集合Vnew和Enew來(lái)描述所得到的最小生成樹。下面對(duì)算法的圖例描述圖例說明不可選可選已選（Vnew）此為原始的加權(quán)連通圖。每條邊一側(cè)的數(shù)字代表其權(quán)值。-頂點(diǎn)D被任意選為起始點(diǎn)。頂點(diǎn)A、B、E和F通過單條邊與D相連。A是距離D最近

11、的頂點(diǎn)，因此將A及對(duì)應(yīng)邊AD以高亮表示。C, GA, B, E, FD下一個(gè)頂點(diǎn)為距離D或A最近的頂點(diǎn)。B距D為9，距A為7，E為15，F(xiàn)為6。因此，F(xiàn)距D或A最近，因此將頂點(diǎn)F與相應(yīng)邊DF以高亮表示。C, GB, E, FA, D算法繼續(xù)重復(fù)上面的步驟。距離A為7的頂點(diǎn)B被高亮表示。CB, E, GA, D, F在當(dāng)前情況下，可以在C、E與G間進(jìn)行選擇。C距B為8，E距B為7，G距F為11。E最近，因此將頂點(diǎn)E與相應(yīng)邊BE高亮表示。無(wú)C, E, GA, D, F, B這里，可供選擇的頂點(diǎn)只有C和G。C距E為5，G距E為9，故選取C，并與邊EC一同高亮表示。無(wú)C, GA, D, F, B, E

12、頂點(diǎn)G是唯一剩下的頂點(diǎn)，它距F為11，距E為9，E最近，故高亮表示G及相應(yīng)邊EG。無(wú)GA, D, F, B, E, C現(xiàn)在，所有頂點(diǎn)均已被選取，圖中綠色部分即為連通圖的最小生成樹。在此例中，最小生成樹的權(quán)值之和為39。無(wú)無(wú)A, D, F, B, E, C, GKruskal算法是一種用來(lái)尋找最小生成樹的算法，由Joseph Kruskal在1956年發(fā)表。用來(lái)解決同樣問題的還有Prim算法和Boruvka算法等。三種算法都是貪婪算法的應(yīng)用。和Boruvka算法不同的地方是，Kruskal算法在圖中存在相同權(quán)值的邊時(shí)也有效。2.算法簡(jiǎn)單描述1).記Graph中有v個(gè)頂點(diǎn)，e個(gè)邊2).新建圖Gra

13、phnew，Graphnew中擁有原圖中相同的e個(gè)頂點(diǎn)，但沒有邊3).將原圖Graph中所有e個(gè)邊按權(quán)值從小到大排序4).循環(huán)：從權(quán)值最小的邊開始遍歷每條邊 直至圖Graph中所有的節(jié)點(diǎn)都在同一個(gè)連通分量中if 這條邊連接的兩個(gè)節(jié)點(diǎn)于圖Graphnew中不在同一個(gè)連通分量中添加這條邊到圖Graphnew中圖例描述：首先第一步，我們有一張圖Graph，有若干點(diǎn)和邊將所有的邊的長(zhǎng)度排序，用排序的結(jié)果作為我們選擇邊的依據(jù)。這里再次體現(xiàn)了貪心算法的思想。資源排序，對(duì)局部最優(yōu)的資源進(jìn)行選擇，排序完成后，我們率先選擇了邊AD。這樣我們的圖就變成了右圖在剩下的變中尋找。我們找到了CE。這里邊的權(quán)重也是5依次

14、類推我們找到了6,7,7，即DF，AB，BE。下面繼續(xù)選擇， BC或者EF盡管現(xiàn)在長(zhǎng)度為8的邊是最小的未選擇的邊。但是現(xiàn)在他們已經(jīng)連通了（對(duì)于BC可以通過CE,EB來(lái)連接，類似的EF可以通過EB,BA,AD,DF來(lái)接連）。所以不需要選擇他們。類似的BD也已經(jīng)連通了（這里上圖的連通線用紅色表示了）。最后就剩下EG和FG了。當(dāng)然我們選擇了EG。最后成功的圖就是右：參考文獻(xiàn) 1 孟彩霞. 計(jì)算機(jī)軟件基礎(chǔ)M. 陜西：西安電子科技大學(xué)出版社, 2003.2 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)M. 北京：清華大學(xué)出版社, 2005.源代碼源文件/引入頭文件 #include stdio.h#include st

15、dlib.h#include malloc.h/定義可能的最大頭節(jié)點(diǎn)數(shù)目 #define MAX_HEADNODE 100/定義最大可能值 #define INTINITY 65535/邊集數(shù)組 #define MAGEDGE 1000/定義當(dāng)前操作節(jié)點(diǎn),從-1做起始值,之后在每次添加頭結(jié)點(diǎn)時(shí)+1 int nowHead = -1;int mapMAX_HEADNODEMAX_HEADNODE;/函數(shù)聲明void menu();void addHeadNode();void addNode();void change();void completeNode();void MiniSpanTre

16、e_Prim();int Find(int *parent,int f);void MiniSpanTree_Kruskal();/定義單個(gè)節(jié)點(diǎn) struct node int adjvex;int data;struct node *next;/給結(jié)構(gòu)體重命名 typedef struct node NODE;/為單鏈表附一個(gè)頭節(jié)點(diǎn)struct headnodeint vexdata;NODE *firstnode;nodeListMAX_HEADNODE;/定義邊集數(shù)組struct Edgeint begin;int end;int weight; /菜單,每次結(jié)束節(jié)點(diǎn)的插入返回此菜單 v

17、oid menu()int n;printf(請(qǐng)選擇你將要進(jìn)行的任務(wù)n1.添加一個(gè)新的頭節(jié)點(diǎn)n2.繼續(xù)添加鄰接節(jié)點(diǎn)n3.完成輸入n4.普里姆算法n5.克魯斯卡爾算法n0.退出程序n);scanf(%d,&n);switch (n)case 0:exit(0);case 1:addHeadNode();break;case 2:addNode();break;case 3:completeNode();break;case 4:MiniSpanTree_Prim();break;case 5:MiniSpanTree_Kruskal();break;default :printf(您輸入的操作信

18、息有誤，請(qǐng)重新輸入n);menu();break; /添加頭節(jié)點(diǎn) void addHeadNode()/頭結(jié)點(diǎn)+1 nowHead+;/無(wú)向圖，雙向不需要判斷是否有鄰接節(jié)點(diǎn) printf(請(qǐng)輸入一個(gè)頭節(jié)點(diǎn)名稱n);/頭節(jié)點(diǎn)信息域 scanf(%d,&(nodeListnowHead.vexdata);/頭節(jié)點(diǎn)指針域 nodeListnowHead.firstnode=NULL;/結(jié)束節(jié)點(diǎn)的添加，返回主菜單 menu(); /添加普通節(jié)點(diǎn)void addNode()/生成一個(gè)節(jié)點(diǎn) NODE *p = (NODE *)malloc(sizeof(NODE);printf(請(qǐng)輸入此節(jié)點(diǎn)相關(guān)信息n);

19、/節(jié)點(diǎn)表示名 printf(請(qǐng)輸入節(jié)點(diǎn)名稱n);scanf(%d,&(p-adjvex);/節(jié)點(diǎn)的權(quán)值 printf(請(qǐng)輸入此節(jié)點(diǎn)的權(quán)值n);scanf(%d,&(p-data);/插入節(jié)點(diǎn) ，反向建立鏈表 p-next=nodeListnowHead.firstnode;nodeListnowHead.firstnode = p;/結(jié)束節(jié)點(diǎn)的添加返回主菜單menu(); /結(jié)束輸入void completeNode()int i=0; NODE *p;printf(已經(jīng)為您建立好的當(dāng)前節(jié)點(diǎn)鄰接表n);/輸出所有已經(jīng)建立好的節(jié)點(diǎn) for(i=0;i,nodeListi.vexdata);p =

20、 nodeListi.firstnode;while(p!=NULL)printf(%d|%d| -,p-adjvex,p-data);p=p-next; printf(n);change();/返回主菜單 menu(); void change()int i,j; NODE *p;for(i=0;i=nowHead;i+)/初始化數(shù)組 for(j=0;jadjvex = p-data;p=p-next; mapii=0;/自己到自己 for(i=0;i=nowHead;i+)for(j=0;j=nowHead;j+)printf(%dt,mapij);printf(n);/Prim算法生成最

21、小生成樹void MiniSpanTree_Prim()int min,i,j,k;int count = nowHead + 1;/VC下需將count改為一個(gè)數(shù)字 int adjvexvcount;/保存相關(guān)頂點(diǎn)下標(biāo),有無(wú)聯(lián)系 int lowcostcount;/保存相關(guān)頂點(diǎn)邊的權(quán)值lowcost0 = 0;/V0作為最小生成樹的根開始遍歷，權(quán)值為0adjvexv0 = 0;/V0第一個(gè)加入/初始化操作for(i=1;icount;i+)lowcosti = map0i;/將鄰接矩陣第0行所有權(quán)值先加入數(shù)組adjvexvi = 0;/ 初始化全部為 V0的下標(biāo) /真正構(gòu)建最小生成樹的過程f

22、or(i=1;icount;i+)min = INTINITY;/初始化最小權(quán)值為65535等不可能的數(shù)值j=1;k=0;/遍歷全部頂點(diǎn)while(j count) /找出lowcost數(shù)組已存儲(chǔ)的最小權(quán)值if(lowcostj!=0 & lowcostj min)/0代表自己和自己連線，min代表無(wú)關(guān)系 min = lowcostj;k=j;/將發(fā)現(xiàn)的最小權(quán)值的下標(biāo)存入k，以待使用 j+; /打印當(dāng)前頂點(diǎn)邊中權(quán)值最小的邊printf(%d,%d),adjvexvk,k);lowcostk = 0; /將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0，表示此頂點(diǎn)已經(jīng)完成任務(wù)，進(jìn)行下一個(gè)頂點(diǎn)的遍歷/鄰接矩陣k行逐個(gè)遍歷全部頂點(diǎn)for(j=1;jcount