建立n個城市間的最小生成樹

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

2、系統(tǒng)子程序及功能設(shè)計- 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 -測試結(jié)果及分析- 14 -測試結(jié)果- 14 -4.2 結(jié)果分析- 17 -4.3 錯誤分析- 17 -源程序- 17 -1 設(shè)計要求 1.1 問題重述選擇6-10個城市模擬在城市之間建立通信網(wǎng)絡(luò)，只需要架設(shè)通信路線就可以，以最低的經(jīng)濟花費建設(shè)通信網(wǎng)，即用Prim算法或Kreskas算法生成一個網(wǎng)的最小生成樹，并計算得到的最小生成樹的代價。 1.

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

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

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

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

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

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

9、一個帶權(quán)圖，其中V為帶權(quán)圖中結(jié)點的集合，E為帶權(quán)圖中的邊的權(quán)值集合。設(shè)置兩個信新的集合U和T，其中U用于存放帶權(quán)圖G的最小生成樹的結(jié)點的集合，T用于存放帶權(quán)圖G的最小生成樹邊的權(quán)值的集合。普利姆算法思想是：令集合U的初值為Uu0（即假設(shè)構(gòu)造最小生成樹時從結(jié)點u0開始），集合T 的初值為T=。從所有結(jié)點u屬于U和結(jié)點v屬于V但不屬于U的帶權(quán)邊中選出具有最小權(quán)值的邊（u，v），將結(jié)點v加入集合U中，將邊（u，v）加入集合T中。如此不斷重復(fù)，當(dāng)U=V時，最小生成樹便構(gòu)造完畢。此時集合U中存在著最小生成樹的結(jié)點，集合T中存放著最小生成樹邊的權(quán)值集合。3 模塊設(shè)計3.1 n個城市連接的最小生成樹選擇6-

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

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

12、數(shù)據(jù)元素ListGet(L,i,x)：取線性表L的第i個數(shù)據(jù)元素，所取得數(shù)據(jù)元素由輸出參數(shù)x帶回，取元素成功返回1，取元素失敗返回0。其約束條件為 0iListLength（L）-1，若i=0，表示取第一個數(shù)據(jù)元素，若i= ListLength（L）-1，表示取最后一個數(shù)據(jù)元素。3.2.2“AdjMGraph.h”鄰接矩陣存儲結(jié)構(gòu)存放邊的信息a. 初始化圖G，n為結(jié)點個數(shù)。 Initiate(AdjMGraph *G, int n)b. 在圖G中插入結(jié)點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é)點v以及與該節(jié)點相關(guān)的所有邊DeleteVerten(AdjMGraph *G,int v)f. 在圖G中尋找序號為v的結(jié)點的第一個鄰接結(jié)點GetFirstVex(AdjMGraph G,int v)g.在圖G中尋找v1結(jié)點的鄰接結(jié)點v2的下一個鄰接結(jié)點.GetNextVex(AdjMGraph G,i

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

15、后依次從集合VU加入到集合U中的結(jié)點為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é)點出發(fā)構(gòu)造的最小生成樹。 (a) (b) (c) (d) (e) (f) (g) (h)3.3 系統(tǒng)子程序及功能設(shè)計3.3.1 定義數(shù)組函數(shù)中定義一個臨時數(shù)組lowcost，數(shù)組元素lowcostv中保存了集合中結(jié)點ui與集合VU中結(jié)點uj的所有邊中當(dāng)前具有最小權(quán)值的邊（u，v）。 3.3.2 定義集合集合U的初值為U=序號為j的結(jié)點。Lowcost的初始值為鄰接

16、矩陣數(shù)組中第j行的值，這樣初始時lowcost中就存放了從集合U中的結(jié)點j到VU中各節(jié)點的權(quán)值。3.3.3 定義lowcost每次從lowcost中尋找具有最小權(quán)值的邊，根據(jù)lowcost的定義，這樣的邊其弧頭結(jié)點必然為集合U中的結(jié)點，其弧尾結(jié)點必然為集合VU中的結(jié)點，當(dāng)選到這樣的邊（u，v）時，就保存其結(jié)點數(shù)據(jù)和權(quán)值數(shù)據(jù)到參數(shù)closevertex中，并將lowcostv置為-1，表示點v加入到了集合U中。3.3.4 修改權(quán)值當(dāng)節(jié)點v從集合VU加入到集合U后，若存在一條邊（u，v），u是集合U的結(jié)點，v是集合VU的節(jié)點，且邊（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ù)組lowcost的動態(tài)變化過程如下所示。其中第一圖表示初始結(jié)點0在集合U中，結(jié)點0到其他結(jié)點有兩條邊，權(quán)值分別為50和60。第二圖表示結(jié)點1加入到集合U中，結(jié)點1加入集合U后，因結(jié)點1到結(jié)點3存在一條權(quán)值為65的邊，該權(quán)值小于原先的無窮大，所以需要把，lowcost3改為65，因結(jié)點1到結(jié)點4存在一條權(quán)值為40的邊，該權(quán)值小于原先的無窮大，所以需要把lowcost4改為40，第三圖表示結(jié)點4加入到集合U后的狀態(tài)，第四圖表示結(jié)點3加入集合u后的狀態(tài)，第五圖表示結(jié)點5加入到集合U后的狀態(tài)，第六圖表示結(jié)點6加入

18、到集合U后的狀態(tài)，最后一圖表示結(jié)點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輸入表示兩個城市間距離RowColWeight rcw返回 圖2 創(chuàng)建鄰接矩陣流程圖判斷程序是否為真Prim算法用鋪助數(shù)組lowCost輸入初始城市序號jfor(i=1;i<n;i+) 初始化lowCosti=G.edgeji從結(jié)點O出發(fā)構(gòu)造最小生成樹結(jié)點尋找當(dāng)前最小權(quán)值的邊所對應(yīng)的弧頭minCost=MaxWeig

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

20、姆算法時需要在創(chuàng)建數(shù)組之前輸入一個城市的結(jié)點序號，在開始時，只是將數(shù)組中的j寫入，并沒有賦初始值，所以在程序運行時出現(xiàn)了錯誤。2、在成功運行從任意結(jié)點構(gòu)造生成樹后，由于需要關(guān)閉運行框后才能進行下一次的構(gòu)造，這是在實際運行中是不允許的，所以要求在程序開始時加一個判斷語句，只要在執(zhí)行完后進行是否繼續(xù)的判斷就可以直接再次運行普利姆算法而不需要關(guā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("順序表已滿無法插入！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("順序表已空無數(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é)點的順序表 */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é)點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越界出錯! 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越界出錯! 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é)點V*/int n=ListLength(G->Vertices),i,j;DataType x;for(i=0;i<n;i+) /*計算刪除后的邊數(shù)*/for(j=0;j<n;j+)if(i=v|j=v) && G->edgeij>0 && G->edgeij<MaxWeight)G->numOfEdges-; /*計算被刪除邊*/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中尋找序號為v的結(jié)點的第一個鄰接結(jié)點*/*如果這樣的鄰接結(jié)點存在，返回該鄰接結(jié)點的序號；否則，返回-1*/int col;if(v<0 | v>G.Vertices.size)prin

29、tf("參數(shù)v1越界出錯!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é)點的鄰接結(jié)點v2的下一個鄰接結(jié)點*/*如果這樣的鄰接結(jié)點存在，返回該鄰接結(jié)點的序號；否則，返回-1*/*v1和v2都是相應(yīng)結(jié)點的序號*/ int col; if(v1<0 | v1>G.

30、Vertices.size | v2<0 | v2>G.Vertices.size) printf("參數(shù)v1或v2越界出錯!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個結(jié)點信息V和e條邊信息E*/int i,k;Initiate(G,n); /*結(jié)點順序表初始化*/for(i=0;i<n;i+)InsertVertex(G,Vi); /*結(jié)點插入*/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的最小生成樹closeVertex*/VerT x;int n=G.Vertices.size,minCost;int *lowCost=(int *)malloc(sizeof(int)*n);int i,j,k; printf("請輸入第一個城市:"); scanf("%d",&j);for(i=0;i<n;i+) /*初始化*/ lowCosti=G.edgeji; /*從結(jié)點j出發(fā)構(gòu)造最小生成樹*/ ListGet(G.Vertices,j,

33、&x); /*取結(jié)點j*/ closeVertexj.vertex=x; /*保存結(jié)點j*/ lowCostj=-1; /*標(biāo)記結(jié)點j*/ for(i=1;i<n;i+)/*結(jié)點尋找當(dāng)前最小權(quán)值的邊所對應(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é)點K*/closeVertexi.vertex=x; /*保存弧頭結(jié)點K*/clo

34、seVertexi.weight=minCost; /*保存相應(yīng)的權(quán)值*/lowCostk=-1; /*標(biāo)記結(jié)點K*/*根據(jù)加入集合U的結(jié)點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