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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、姆算法時需要在創建數組之前輸入一個城市的結點序號，在開始時，只是將數組中的j寫入，并沒有賦初始值，所以在程序運行時出現了錯誤。2、在成功運行從任意結點構造生成樹后，由于需要關閉運行框后才能進行下一次的構造，這是在實際運行中是不允許的，所以要求在程序開始時加一個判斷語句，只要在執行完后進行是否繼續的判斷就可以直接再次運行普利姆算法而不需要關閉運行框后再重新運行程序。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("參數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("順序表已空無數據可刪！n");return 0;else if(i<0|i>L->size-1)printf("參數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("參數i不合法！n");return 0; else *x=L.listi; return 1; typedef structSeqList Vertices; /* 存放結點的順序表 */int edgeMaxVerticesMaxVertices; /* 存放邊的鄰結矩陣地 */int numOfEdges; /* 邊的條數 */AdjMGraph; /* 圖的結構體定義 */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; /* 邊的條數置為0 */ListInitiate(&G->Vertices); /*順序表初始化 */void InsertVertex(AdjMGraph *G, DataType vertex) /* v在圖G中插入結點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>的權為weight */if(v1<0 | v1>G->Vertices.size | v2>G->Vertices.size|v2<0)printf("參數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("摻數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) /*刪除結點V*/int n=ListLength(G->Vertices),i,j;DataType x;for(i=0;i<n;i+) /*計算刪除后的邊數*/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的結點的第一個鄰接結點*/*如果這樣的鄰接結點存在，返回該鄰接結點的序號；否則，返回-1*/int col;if(v<0 | v>G.Vertices.size)prin

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

30、Vertices.size | v2<0 | v2>G.Vertices.size) printf("參數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; /*行下標*/int col; /*列下標*/int weight; /*權值*/RowColWeight; /*邊信息結構體

31、定義*/void CreatGraph(AdjMGraph *G,char V,int n,RowColWeight E,int e)/*在圖G中插入v個結點信息V和e條邊信息E*/int i,k;Initiate(G,n); /*結點順序表初始化*/for(i=0;i<n;i+)InsertVertex(G,Vi); /*結點插入*/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)/*用普里姆算法建立帶權圖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; /*從結點j出發構造最小生成樹*/ ListGet(G.Vertices,j,

33、&x); /*取結點j*/ closeVertexj.vertex=x; /*保存結點j*/ lowCostj=-1; /*標記結點j*/ for(i=1;i<n;i+)/*結點尋找當前最小權值的邊所對應的弧頭K*/minCost=MaxWeight;for(j=0;j<n;j+) if(lowCostj<minCost && lowCostj>0) minCost=lowCostj; k=j;ListGet(G.Vertices,k,&x); /*取弧頭結點K*/closeVertexi.vertex=x; /*保存弧頭結點K*/clo

34、seVertexi.weight=minCost; /*保存相應的權值*/lowCostk=-1; /*標記結點K*/*根據加入集合U的結點K修改lowCost中的數值*/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