建立n個(gè)城市間的最小生成樹(shù)

1、目 錄設(shè)計(jì)要求- 1 -問(wèn)題重述- 1 -基本要求- 2 -概要設(shè)計(jì)- 2 -2.1 主界面的設(shè)計(jì)- 2 -2.2 存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)本系統(tǒng)- 3 -2.2.1 順序表的基本概念- 3 -2.2.2 圖的鄰接矩陣的基本概念- 4 -2.2.3 最小生成樹(shù)的基本概念- 5 -模塊設(shè)計(jì)- 6 -3.1 n個(gè)城市連接的最小生成樹(shù)- 6 -3.2 模塊作用用途中的頂點(diǎn)表示- 6 -3.3 模塊及模塊調(diào)用關(guān)系- 6 -3.2.1 “SeqList.h”順序存儲(chǔ)結(jié)構(gòu)存放結(jié)點(diǎn)信息- 7 -3.2.2“AdjMGraph.h”鄰接矩陣存儲(chǔ)結(jié)構(gòu)存放邊的信息- 7 -3.2.3 最小生成樹(shù)的生成過(guò)程- 8 -3.3

2、系統(tǒng)子程序及功能設(shè)計(jì)- 9 -3.3.1 定義數(shù)組- 9 -3.3.2 定義集合- 10 -3.3.3 定義lowcost- 10 -3.3.4 修改權(quán)值- 10 -3.3.5 帶權(quán)圖- 10 -3.4 算法描述- 12 -3.4.1 流程圖- 12 -測(cè)試結(jié)果及分析- 14 -測(cè)試結(jié)果- 14 -4.2 結(jié)果分析- 17 -4.3 錯(cuò)誤分析- 17 -源程序- 17 -1 設(shè)計(jì)要求 1.1 問(wèn)題重述選擇6-10個(gè)城市模擬在城市之間建立通信網(wǎng)絡(luò)，只需要架設(shè)通信路線就可以，以最低的經(jīng)濟(jì)花費(fèi)建設(shè)通信網(wǎng)，即用Prim算法或Kreskas算法生成一個(gè)網(wǎng)的最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。 1.

3、2 基本要求u 城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本上的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。要求在屏幕上顯示得到的最小生成樹(shù)中包括那些城市間的道路，并顯示得到的最小生成樹(shù)的代價(jià)。u 表示城市間距離網(wǎng)的鄰接矩陣u 最小生成樹(shù)中包括的邊及其權(quán)值，并顯示得到的最小生成樹(shù)的代價(jià)。2 概要設(shè)計(jì)為了實(shí)現(xiàn)以上功能，可以從以下主界面構(gòu)造、存儲(chǔ)結(jié)構(gòu)采用、系統(tǒng)功能設(shè)置等三個(gè)方面進(jìn)行分析設(shè)計(jì)。將圖的結(jié)點(diǎn)信息存放在一個(gè)順序表中，圖的邊信息存儲(chǔ)在一個(gè)二維數(shù)組edgeMaxVerticesMaxVertices中，這樣就實(shí)現(xiàn)了用鄰接矩陣存放城市間的距離網(wǎng)。在P

4、rim算法的函數(shù)用兩個(gè)參數(shù)，一個(gè)是圖G為鄰接矩陣存儲(chǔ)結(jié)構(gòu)的圖；另一個(gè)是通過(guò)函數(shù)得到的最小生成樹(shù)的結(jié)點(diǎn)數(shù)據(jù)和相應(yīng)結(jié)點(diǎn)的邊的權(quán)值數(shù)據(jù)closeVertex.2.1 主界面的設(shè)計(jì)為了 首先需要設(shè)計(jì)一個(gè)主界面子程序，以鏈接系統(tǒng)的各項(xiàng)子功能運(yùn)行界面如圖1所示 圖12.2 存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)本系統(tǒng)采用圖結(jié)構(gòu)類型，存儲(chǔ)抽象n個(gè)城市模擬在城市之間建立通信網(wǎng)絡(luò)，其中各城市用鄰接矩陣類型存儲(chǔ)。2.2.1 順序表的基本概念 當(dāng)采用C語(yǔ)言描述數(shù)據(jù)結(jié)構(gòu)時(shí)問(wèn)題時(shí)，實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)的方法是使用數(shù)組。數(shù)組把線性表的數(shù)據(jù)元素存儲(chǔ)在一塊連續(xù)地址空間的內(nèi)存單元內(nèi)，這樣，線性表中邏輯上相鄰的數(shù)據(jù)元素在物理存儲(chǔ)地址上也相鄰，數(shù)據(jù)元素間的邏

5、輯上的前驅(qū)，后繼邏輯關(guān)系就表現(xiàn)在數(shù)據(jù)元素的存儲(chǔ)單元的物理前后位置關(guān)系上。 數(shù)組有靜態(tài)數(shù)組和動(dòng)態(tài)數(shù)組兩種。靜態(tài)數(shù)組存儲(chǔ)空間的申請(qǐng)和釋放有系統(tǒng)自動(dòng)完成，動(dòng)態(tài)數(shù)組存儲(chǔ)空間的申請(qǐng)和釋放由用戶調(diào)用系統(tǒng)函數(shù)完成。無(wú)論是靜態(tài)數(shù)組還是動(dòng)態(tài)數(shù)組，其功能都是向系統(tǒng)申請(qǐng)一塊地址連續(xù)的有限空間，只是申請(qǐng)的方法不同，順序表一般采用靜態(tài)數(shù)組方法實(shí)現(xiàn)數(shù)據(jù)元素的存儲(chǔ)。 順序表定義結(jié)構(gòu)體如下： Typedef struct DataType listMaxsize; Int size;SeqList;其中，DataType為數(shù)組（即數(shù)據(jù)元素）的數(shù)據(jù)類型，Maxsize表示數(shù)組的最大元素個(gè)數(shù)，list表示順序表的數(shù)組名，size

6、表示順序表中當(dāng)前存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)，它必須滿足size<= Maxsize，SeqList是該結(jié)構(gòu)體的名稱。2.2.2 圖的鄰接矩陣的基本概念由圖的定義可知，圖的信息包括兩部分，圖中結(jié)點(diǎn)的信息和描述之間關(guān)系的邊的信息。結(jié)點(diǎn)信息的描述問(wèn)題，是一個(gè)簡(jiǎn)單的表存儲(chǔ)結(jié)構(gòu)問(wèn)題。對(duì)于一個(gè)有n個(gè)節(jié)點(diǎn)的圖，由于每個(gè)結(jié)點(diǎn)都可能與其他n-1個(gè)結(jié)點(diǎn)成為鄰接結(jié)點(diǎn)，所以邊之間關(guān)系的描述問(wèn)題，實(shí)際上是一個(gè)n*n矩陣的計(jì)算機(jī)存儲(chǔ)表示問(wèn)題。在圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)中，節(jié)點(diǎn)信息使用一維數(shù)組存儲(chǔ)，邊的鄰接矩陣使用二維數(shù)組存儲(chǔ)，無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣。當(dāng)圖中結(jié)點(diǎn)數(shù)目較小且邊較多時(shí)，采用圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)效率較高；當(dāng)圖中

7、結(jié)點(diǎn)數(shù)目較大且邊的數(shù)目遠(yuǎn)小于相同結(jié)點(diǎn)的完全圖的邊數(shù)時(shí)，采用圖的鄰接表存儲(chǔ)結(jié)構(gòu)效率較高。圖的結(jié)構(gòu)體定義如下：typedef struct SeqList Vertices; int edgeMaxVertices MaxVertices; int numOfEdges;AdjMGraph;2.2.3 最小生成樹(shù)的基本概念 一個(gè)有n個(gè)結(jié)點(diǎn)的連通圖的生成樹(shù)是原圖的極小連通子圖，他包含原圖中的所有n個(gè)結(jié)點(diǎn)，并且保持圖連通的最少的邊。 由生成樹(shù)的定義可知：（1）若再生成樹(shù)中刪除一條邊就會(huì)使該生成樹(shù)因變成非連通圖而不再滿足生成樹(shù)的定義；（2）若在生成樹(shù)中增加一條邊就會(huì)使生成樹(shù)中存在回路而不再滿足生成樹(shù)的定

8、義；（3）一個(gè)連通圖的生成樹(shù)可能得到不同的生成樹(shù)。使用不同的尋找方法可以得到不同的生成樹(shù)。另外，從不同的初始結(jié)點(diǎn)出發(fā)也可以得到不同的生成樹(shù)。 從生成樹(shù)的定義顯然可以證明，對(duì)于有n個(gè)結(jié)點(diǎn)的無(wú)向連通圖，無(wú)論他的生成樹(shù)的形狀如何，一定有且只有n-1條邊。 如果無(wú)向連通圖是一條帶權(quán)圖，那么他的所有生成樹(shù)中必有一顆邊的權(quán)值總和為最小的生成樹(shù)，稱這棵生成樹(shù)為最小代價(jià)生成樹(shù)，簡(jiǎn)稱最小生成樹(shù)。 從最小生成樹(shù)的定義可知，構(gòu)造有n個(gè)結(jié)點(diǎn)的無(wú)向連通帶權(quán)圖的最小生成樹(shù)必須滿足以下三點(diǎn)：（1）構(gòu)造的最小生成樹(shù)必須包括n個(gè)結(jié)點(diǎn)（2）構(gòu)造的最小生成樹(shù)中有且只有n-1條邊（3）構(gòu)造的最小生成樹(shù)中不存在回路假設(shè)G=(V,E)為

9、一個(gè)帶權(quán)圖，其中V為帶權(quán)圖中結(jié)點(diǎn)的集合，E為帶權(quán)圖中的邊的權(quán)值集合。設(shè)置兩個(gè)信新的集合U和T，其中U用于存放帶權(quán)圖G的最小生成樹(shù)的結(jié)點(diǎn)的集合，T用于存放帶權(quán)圖G的最小生成樹(shù)邊的權(quán)值的集合。普利姆算法思想是：令集合U的初值為Uu0（即假設(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)造完畢。此時(shí)集合U中存在著最小生成樹(shù)的結(jié)點(diǎn)，集合T中存放著最小生成樹(shù)邊的權(quán)值集合。3 模塊設(shè)計(jì)3.1 n個(gè)城市連接的最小生成樹(shù)選擇6-

10、10個(gè)城市模擬在城市之間建立通信網(wǎng)絡(luò)，只需要架設(shè)通信路線就可以，以最低的經(jīng)濟(jì)花費(fèi)建設(shè)通信網(wǎng)，即生成一個(gè)網(wǎng)的最小生成樹(shù)，各城市分別用字母AG表示。3.2 模塊作用用途中的頂點(diǎn)表示頭文件用來(lái)存放鄰接矩陣存儲(chǔ)結(jié)構(gòu)定義以及相應(yīng)的圖的操作函數(shù)與圖的創(chuàng)建及普里姆函數(shù)的設(shè)計(jì)。主函數(shù)“prim.cpp”來(lái)測(cè)試程序。3.3 模塊及模塊調(diào)用關(guān)系3.2.1 “SeqList.h”順序存儲(chǔ)結(jié)構(gòu)存放結(jié)點(diǎn)信息a.初始化ListInitiate(L)：初始化線性表L。b.求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)ListLength（L）：函數(shù)返回線性表L的當(dāng)前數(shù)據(jù)元素的個(gè)數(shù)c.插入數(shù)據(jù)元素ListInsert(L,i,x)：在現(xiàn)象表L的第i個(gè)數(shù)

11、據(jù)前插入數(shù)據(jù)元素x，如果插入成功返回1，插入失敗返回0。其約束條件為0iListLength（L），即若i=0，表示在第一個(gè)元素之前插入數(shù)據(jù)元素x，若i= ListLength（L）-1，表示在最后一個(gè)元素前插入數(shù)據(jù)元素x，若i= ListLength（L），表示在最后一個(gè)元素之后插入數(shù)據(jù)元素x。d.刪除數(shù)據(jù)元素ListDelete(L,i,x)：刪除線性表L的第i個(gè)元素，所刪除的數(shù)據(jù)元素由輸出參數(shù)x帶回。如果刪除成功返回1，刪除失敗返回0，其約束條件為0iListLength（L）-1，若i=0，表示刪除第一個(gè)數(shù)據(jù)元素，若i= ListLength（L）-1，表示刪除最后一個(gè)數(shù)據(jù)元素。e.取

12、數(shù)據(jù)元素ListGet(L,i,x)：取線性表L的第i個(gè)數(shù)據(jù)元素，所取得數(shù)據(jù)元素由輸出參數(shù)x帶回，取元素成功返回1，取元素失敗返回0。其約束條件為 0iListLength（L）-1，若i=0，表示取第一個(gè)數(shù)據(jù)元素，若i= ListLength（L）-1，表示取最后一個(gè)數(shù)據(jù)元素。3.2.2“AdjMGraph.h”鄰接矩陣存儲(chǔ)結(jié)構(gòu)存放邊的信息a. 初始化圖G，n為結(jié)點(diǎn)個(gè)數(shù)。 Initiate(AdjMGraph *G, int n)b. 在圖G中插入結(jié)點(diǎn)vertex InsertVertex(AdjMGraph *G, DataType vertex)c. 在圖G中插入邊<v1,v2&g

13、t;，邊<v1,v2>的權(quán)值為weightInsertEdge(AdjMGraph *G, int v1,int v2,int weight)d. 在圖G中刪除邊<v1,v2>DeleteEdge(AdjMGraph *G,int v1,int v2)e. 刪除圖G中的結(jié)點(diǎn)v以及與該節(jié)點(diǎn)相關(guān)的所有邊DeleteVerten(AdjMGraph *G,int v)f. 在圖G中尋找序號(hào)為v的結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)GetFirstVex(AdjMGraph G,int v)g.在圖G中尋找v1結(jié)點(diǎn)的鄰接結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn).GetNextVex(AdjMGraph G,i

14、nt v1,int v2)3.2.3 最小生成樹(shù)的生成過(guò)程 下圖中給出了用普利姆算法構(gòu)造最小生成樹(shù)的過(guò)程。(a)為一個(gè)有7個(gè)結(jié)點(diǎn)10條邊的無(wú)向邊的帶權(quán)圖。初始集合U=A，集合VU=B，C，D，E，F(xiàn)，G，T=，如圖（b）所示，此時(shí)，存在兩條一個(gè)結(jié)點(diǎn)在U、另一個(gè)結(jié)點(diǎn)在集合VU中的邊，具有最小權(quán)值的邊（A，B），權(quán)值為50，把結(jié)點(diǎn)B從VU加入到集合U中，把邊（A，B）加入到T中，如圖（c）所示，在所有以u(píng)為集合U中結(jié)點(diǎn)、v為集合VU中結(jié)點(diǎn)的邊（u，v）中尋找具有最小權(quán)值的邊（u，v），尋找到的是（B,E），權(quán)值為40，把結(jié)點(diǎn)E從集合VU中加入到集合U中，把邊（B,E）加入到T中，如圖（d）所示，隨

15、后依次從集合VU加入到集合U中的結(jié)點(diǎn)為D，F(xiàn)，G，C，依次加入到T中的邊為（E，D），權(quán)值為50，（D,F）權(quán)值為30，（D,G），權(quán)值為42，（G，C），權(quán)值為45，分別如圖（e）（f）（g）（h）所示，最后得到的圖（h）就是從A結(jié)點(diǎn)出發(fā)構(gòu)造的最小生成樹(shù)。 (a) (b) (c) (d) (e) (f) (g) (h)3.3 系統(tǒng)子程序及功能設(shè)計(jì)3.3.1 定義數(shù)組函數(shù)中定義一個(gè)臨時(shí)數(shù)組lowcost，數(shù)組元素lowcostv中保存了集合中結(jié)點(diǎn)ui與集合VU中結(jié)點(diǎn)uj的所有邊中當(dāng)前具有最小權(quán)值的邊（u，v）。 3.3.2 定義集合集合U的初值為U=序號(hào)為j的結(jié)點(diǎn)。Lowcost的初始值為鄰接

16、矩陣數(shù)組中第j行的值，這樣初始時(shí)lowcost中就存放了從集合U中的結(jié)點(diǎn)j到VU中各節(jié)點(diǎn)的權(quán)值。3.3.3 定義lowcost每次從lowcost中尋找具有最小權(quán)值的邊，根據(jù)lowcost的定義，這樣的邊其弧頭結(jié)點(diǎn)必然為集合U中的結(jié)點(diǎn)，其弧尾結(jié)點(diǎn)必然為集合VU中的結(jié)點(diǎn)，當(dāng)選到這樣的邊（u，v）時(shí)，就保存其結(jié)點(diǎn)數(shù)據(jù)和權(quán)值數(shù)據(jù)到參數(shù)closevertex中，并將lowcostv置為-1，表示點(diǎn)v加入到了集合U中。3.3.4 修改權(quán)值當(dāng)節(jié)點(diǎn)v從集合VU加入到集合U后，若存在一條邊（u，v），u是集合U的結(jié)點(diǎn)，v是集合VU的節(jié)點(diǎn)，且邊（u，v）較原先lowcostv的權(quán)值更小，則用這樣的權(quán)值修改原先l

17、owcostv中相應(yīng)權(quán)值。3.3.5 帶權(quán)圖以圖（a）所示的帶權(quán)圖為例，調(diào)用普利姆函數(shù)時(shí)數(shù)組lowcost的動(dòng)態(tài)變化過(guò)程如下所示。其中第一圖表示初始結(jié)點(diǎn)0在集合U中，結(jié)點(diǎn)0到其他結(jié)點(diǎn)有兩條邊，權(quán)值分別為50和60。第二圖表示結(jié)點(diǎn)1加入到集合U中，結(jié)點(diǎn)1加入集合U后，因結(jié)點(diǎn)1到結(jié)點(diǎn)3存在一條權(quán)值為65的邊，該權(quán)值小于原先的無(wú)窮大，所以需要把，lowcost3改為65，因結(jié)點(diǎn)1到結(jié)點(diǎn)4存在一條權(quán)值為40的邊，該權(quán)值小于原先的無(wú)窮大，所以需要把lowcost4改為40，第三圖表示結(jié)點(diǎn)4加入到集合U后的狀態(tài)，第四圖表示結(jié)點(diǎn)3加入集合u后的狀態(tài)，第五圖表示結(jié)點(diǎn)5加入到集合U后的狀態(tài)，第六圖表示結(jié)點(diǎn)6加入

18、到集合U后的狀態(tài)，最后一圖表示結(jié)點(diǎn)3加入到集合U后的狀態(tài)。 lowcost lowcost lowcost lowcost lowcost lowcost lowcost 3.4 算法描述3.4.1 流程圖創(chuàng)建用鄰接矩陣表示的城市道路網(wǎng)輸入城市屬N=7道路數(shù)e=20輸入城市a輸入表示兩個(gè)城市間距離RowColWeight rcw返回 圖2 創(chuàng)建鄰接矩陣流程圖判斷程序是否為真Prim算法用鋪助數(shù)組lowCost輸入初始城市序號(hào)jfor(i=1;i<n;i+) 初始化lowCosti=G.edgeji從結(jié)點(diǎn)O出發(fā)構(gòu)造最小生成樹(shù)結(jié)點(diǎn)尋找當(dāng)前最小權(quán)值的邊所對(duì)應(yīng)的弧頭minCost=MaxWeig

19、ht輸出找到的道路標(biāo)記城市輸出總代價(jià)判斷是否繼續(xù)：1-繼續(xù)；2-退出1：返回程序開(kāi)始處2：退出結(jié)束 Prim算法流程圖4 測(cè)試結(jié)果及分析4.1測(cè)試結(jié)果4.2 結(jié)果分析當(dāng)從一個(gè)第一個(gè)頂點(diǎn)開(kāi)始以此作為生成樹(shù)的初始狀態(tài)，然后找出與其之間權(quán)值最小的頂點(diǎn)2并把頂點(diǎn)2添加到該生成樹(shù)中，以此類推找出與頂點(diǎn)2之間權(quán)值最小的頂點(diǎn)。再把找出的頂點(diǎn)添加到生成樹(shù)中直到最后一個(gè)頂點(diǎn)添加到生成樹(shù)上是得到所求的生成數(shù)即為最小生成樹(shù)。4.3 錯(cuò)誤分析在本次課程設(shè)計(jì)的過(guò)程中，出現(xiàn)諸多錯(cuò)誤，比如分號(hào)沒(méi)有打以及一些錯(cuò)打和少打的情況，在此不做一一的介紹，只介紹一些較大的錯(cuò)誤。1、本應(yīng)從任一節(jié)點(diǎn)接入均可以構(gòu)造最小生成樹(shù)，所以在運(yùn)行普利

20、姆算法時(shí)需要在創(chuàng)建數(shù)組之前輸入一個(gè)城市的結(jié)點(diǎn)序號(hào)，在開(kāi)始時(shí)，只是將數(shù)組中的j寫入，并沒(méi)有賦初始值，所以在程序運(yùn)行時(shí)出現(xiàn)了錯(cuò)誤。2、在成功運(yùn)行從任意結(jié)點(diǎn)構(gòu)造生成樹(shù)后，由于需要關(guān)閉運(yùn)行框后才能進(jìn)行下一次的構(gòu)造，這是在實(shí)際運(yùn)行中是不允許的，所以要求在程序開(kāi)始時(shí)加一個(gè)判斷語(yǔ)句，只要在執(zhí)行完后進(jìn)行是否繼續(xù)的判斷就可以直接再次運(yùn)行普利姆算法而不需要關(guān)閉運(yùn)行框后再重新運(yùn)行程序。5 源程序頭文件：AdjMGraph.htypedef int DataType;typedef struct DataType listMaxSize;int size;SeqList;void ListInitiate(SeqLi

21、st *L)L->size=0;int ListLength(SeqList L)return L.size;int ListInsert(SeqList *L,int i,DataType x)int j;if(L->size>=MaxSize)printf("順序表已滿無(wú)法插入！n");return 0;else if(i<0|i>L->size)printf("參數(shù)i不合法！n");return 0;else for(j=L->size;j>i;j-) L->listj=L->listj-

22、1; L->listi=x; L->size+; return 1;int ListDelete(SeqList *L,int i,DataType*x)int j;if(L->size<=0)printf("順序表已空無(wú)數(shù)據(jù)可刪！n");return 0;else if(i<0|i>L->size-1)printf("參數(shù)i不合法！n");return 0;else*x=L->listi;for(j=i;j<L->size;j+) L->listj=L->listj+1; L-&g

23、t;size-; return 1; int ListGet(SeqList L,int i,char*x) if(i<0|i>L.size-1)printf("參數(shù)i不合法！n");return 0; else *x=L.listi; return 1; typedef structSeqList Vertices; /* 存放結(jié)點(diǎn)的順序表 */int edgeMaxVerticesMaxVertices; /* 存放邊的鄰結(jié)矩陣地 */int numOfEdges; /* 邊的條數(shù) */AdjMGraph; /* 圖的結(jié)構(gòu)體定義 */void Initiat

24、e(AdjMGraph *G, int n) /* 初始化 */int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)if(i=j) G->edgeij=0;else G->edgeij=MaxWeight;G->numOfEdges=0; /* 邊的條數(shù)置為0 */ListInitiate(&G->Vertices); /*順序表初始化 */void InsertVertex(AdjMGraph *G, DataType vertex) /* v在圖G中插入結(jié)點(diǎn)vertex */ListInsert(&G->Ve

25、rtices, G->Vertices.size,vertex); /* 順序表尾插入 */void InsertEdge(AdjMGraph *G, int v1,int v2,int weight) /*在圖G中插入邊<v1,v2>，邊<v1,v2>的權(quán)為weight */if(v1<0 | v1>G->Vertices.size | v2>G->Vertices.size|v2<0)printf("參數(shù)v1或v2越界出錯(cuò)! n");exit(1);G->edgev1v2=weight;G->

26、numOfEdges+;void DeleteEdge(AdjMGraph *G,int v1,int v2)/*在圖G中刪除邊<v1,v2> */if(v1<0 | v1>G->Vertices.size | v2<0 | v2>G->Vertices.size | v1=v2)printf("摻數(shù)v1或v2越界出錯(cuò)! n");exit(1);if(G->edgev1v2=MaxWeight | v1=v2)printf("該邊不存在!n");exit(0);G->edgev1v2=MaxWe

27、ight;G->numOfEdges-;void DeleteVertex(AdjMGraph *G,int v) /*刪除結(jié)點(diǎn)V*/int n=ListLength(G->Vertices),i,j;DataType x;for(i=0;i<n;i+) /*計(jì)算刪除后的邊數(shù)*/for(j=0;j<n;j+)if(i=v|j=v) && G->edgeij>0 && G->edgeij<MaxWeight)G->numOfEdges-; /*計(jì)算被刪除邊*/for(i=v;i<n;i+) /*刪除第v行

28、*/for(j=0;j<n;j+)G->edgeij=G->edgei+1j;for(i=0;i<n;i+) /*刪除第v列*/for(j=v;j<n;j+)G->edgeij=G->edgeij+1;ListDelete(&G->Vertices,v,&x);int GetFirstVex(AdjMGraph G,int v)/*在圖G中尋找序號(hào)為v的結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)*/*如果這樣的鄰接結(jié)點(diǎn)存在，返回該鄰接結(jié)點(diǎn)的序號(hào)；否則，返回-1*/int col;if(v<0 | v>G.Vertices.size)prin

29、tf("參數(shù)v1越界出錯(cuò)!n");exit(1);for(col=0;col<G.Vertices.size;col+)if(G.edgevcol>0 && G.edgevcol<MaxWeight) return col;return -1;int GetNextVex(AdjMGraph G,int v1,int v2)/*在圖G中尋找v1結(jié)點(diǎn)的鄰接結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn)*/*如果這樣的鄰接結(jié)點(diǎn)存在，返回該鄰接結(jié)點(diǎn)的序號(hào)；否則，返回-1*/*v1和v2都是相應(yīng)結(jié)點(diǎn)的序號(hào)*/ int col; if(v1<0 | v1>G.

30、Vertices.size | v2<0 | v2>G.Vertices.size) printf("參數(shù)v1或v2越界出錯(cuò)!n"); exit(1); for(col=v2+1;col<G.Vertices.size;col+) if(G.edgev1col>0 && G.edgev1col<MaxWeight) return col; return -1;typedef structint row; /*行下標(biāo)*/int col; /*列下標(biāo)*/int weight; /*權(quán)值*/RowColWeight; /*邊信息結(jié)構(gòu)體

31、定義*/void CreatGraph(AdjMGraph *G,char V,int n,RowColWeight E,int e)/*在圖G中插入v個(gè)結(jié)點(diǎn)信息V和e條邊信息E*/int i,k;Initiate(G,n); /*結(jié)點(diǎn)順序表初始化*/for(i=0;i<n;i+)InsertVertex(G,Vi); /*結(jié)點(diǎn)插入*/for(k=0;k<e;k+)InsertEdge(G,Ek.row,Ek.col,Ek.weight); /*邊插入*/typedef structVerT vertex;int weight;MinSpanTree;void Prim(AdjMG

32、raph G, MinSpanTree closeVertex)/*用普里姆算法建立帶權(quán)圖G的最小生成樹(shù)closeVertex*/VerT x;int n=G.Vertices.size,minCost;int *lowCost=(int *)malloc(sizeof(int)*n);int i,j,k; printf("請(qǐng)輸入第一個(gè)城市:"); scanf("%d",&j);for(i=0;i<n;i+) /*初始化*/ lowCosti=G.edgeji; /*從結(jié)點(diǎn)j出發(fā)構(gòu)造最小生成樹(shù)*/ ListGet(G.Vertices,j,

33、&x); /*取結(jié)點(diǎn)j*/ closeVertexj.vertex=x; /*保存結(jié)點(diǎn)j*/ lowCostj=-1; /*標(biāo)記結(jié)點(diǎn)j*/ for(i=1;i<n;i+)/*結(jié)點(diǎn)尋找當(dāng)前最小權(quán)值的邊所對(duì)應(yīng)的弧頭K*/minCost=MaxWeight;for(j=0;j<n;j+) if(lowCostj<minCost && lowCostj>0) minCost=lowCostj; k=j;ListGet(G.Vertices,k,&x); /*取弧頭結(jié)點(diǎn)K*/closeVertexi.vertex=x; /*保存弧頭結(jié)點(diǎn)K*/clo

34、seVertexi.weight=minCost; /*保存相應(yīng)的權(quán)值*/lowCostk=-1; /*標(biāo)記結(jié)點(diǎn)K*/*根據(jù)加入集合U的結(jié)點(diǎn)K修改lowCost中的數(shù)值*/for(j=0;j<n;j+)if(G.edgekj<lowCostj)lowCostj=G.edgekj;主文件：prim.cpp#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef char VerT;#define MaxSize 100 #define MaxVertices 10#define MaxWeight 10000#define N 7#include"AdjMGraph.h"void main(void)while(1)AdjMGraph g;char a='A','B','C','D','E','F','G'RowColWeight rcw=0