構(gòu)造可以使n個城市連接的最小生成樹

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題目：構(gòu)造可以使設(shè)計題目：構(gòu)造可以使 n n 個城市連接的最小生成個城市連接的最小生成樹樹姓名：姓名： 學(xué)號：學(xué)號：專業(yè)：物聯(lián)網(wǎng)工程（嵌入式培養(yǎng)）專業(yè)：物聯(lián)網(wǎng)工程（嵌入式培養(yǎng)）院系：計算機(jī)技術(shù)與科學(xué)學(xué)院院系：計算機(jī)技術(shù)與科學(xué)學(xué)院班級：班級：14051405指導(dǎo)教師：指導(dǎo)教師： 20162016 年年 0101 月月 0909 日日 第 1 頁 共 17 頁摘要本次課程設(shè)計的要求是給定一個地區(qū)的本次課程設(shè)計的要求是給定一個地區(qū)的 n n 個城市間的距離個城市間的距離網(wǎng)，用網(wǎng)，用 PrimPrim 算法建立最小生成樹，并計算得到的最小生成算法建立最小生成樹，并計算得到的最小

2、生成樹的代價。將該地區(qū)的城市用頂點表示，城市間的公路用樹的代價。將該地區(qū)的城市用頂點表示，城市間的公路用邊表示，公路的長度作為邊的權(quán)值，最終這個問題可以歸邊表示，公路的長度作為邊的權(quán)值，最終這個問題可以歸結(jié)為網(wǎng)圖中，求頂點結(jié)為網(wǎng)圖中，求頂點 A A 到頂點到頂點 B B 的所有路徑中，邊的權(quán)值的所有路徑中，邊的權(quán)值之和最少的那條路徑。之和最少的那條路徑。關(guān)鍵詞：關(guān)鍵詞：最小生成樹最小生成樹 PrimPrim 算法算法 C+C+語言源程序語言源程序第 2 頁 共 17 頁AbstractTheThe currcurriculumiculum designdesign requirementsre

3、quirements isis givengiven a a regionregion n n city,city, thethe distancedistance betweenbetween thethe netnet withwith thethe PrimPrim algorithmalgorithm toto establishestablish minimumminimum spanningspanning tree,tree, andand calculatedcalculated thethe priceprice ofof minimumminimum spanningspa

4、nning tree.tree. CitiesCities inin thethe regionregion withwith vertexvertex said,said, betweenbetween highwayhighway inin thethe citycity edge,edge, saidsaid thethe lengthlength ofof thethe roadroad asas thethe edgeedge ofof thethe rightright values,values, finallyfinally thethe problemproblem canc

5、an bebe summedsummed upup inin networknetwork diagram,diagram, andand allall thethe pathspaths ofof vertexvertex A A toto B,B, thethe edgeedge ofof thethe weightsweights ofof thethe sumsum ofof thethe minimumminimum path.path.Keywords:Keywords: minimumminimum spanningspanning treetreePrimPrim algori

6、thmalgorithm C+C+ languagelanguage sourcesource programprogram第 3 頁 共 17 頁目 錄一、問題描述一、問題描述 .41.1 題目內(nèi)容題目內(nèi)容 .41.2 基本要求基本要求 .4二、需求分析二、需求分析 .4三、概要設(shè)計三、概要設(shè)計 .43.1 鄰接矩陣的建立鄰接矩陣的建立.53.2 圖的建立圖的建立 .53.3 求最小生成樹求最小生成樹.6四、數(shù)據(jù)結(jié)構(gòu)設(shè)計四、數(shù)據(jù)結(jié)構(gòu)設(shè)計.7五、算法設(shè)計五、算法設(shè)計 .85.1 算法分析算法分析 .85.2 算法實現(xiàn)算法實現(xiàn) .8六、程序測試與實現(xiàn)六、程序測試與實現(xiàn) .96.1 主程序主程序.

7、96.2 測試結(jié)果測試結(jié)果.10七、調(diào)試分析七、調(diào)試分析.10八、遇到的問題及解決辦法八、遇到的問題及解決辦法.10九、心得體會九、心得體會.10十、附錄十、附錄 .11第 4 頁 共 17 頁一、一、 問題描述問題描述1 題目內(nèi)容：給定一個地區(qū)的 n 個城市間的距離網(wǎng)，用 Prim 算法建立最小生成樹，并計算得到的最小生成樹的代價。2 基本要求：a) 城市間的距離網(wǎng)采用鄰接矩陣表示，若兩個城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大值。 （要求至少 10 個城市，15 條邊）b) 最小生成樹中包括的邊及其權(quán)值，并顯示得到的最小生成樹的代價。二、二、 需求分析需求分析本程序的功能包

8、括圖的建立（采用鄰接矩陣存儲）和求最小生成樹。1圖的建立涉及到頂點數(shù)組 datan和鄰接矩陣 Edgenn，頂點數(shù)組運(yùn)用順序表完成，操作有：頂點的插入即順序表的插入；鄰接矩陣的建立，操作有：插入弧和對應(yīng)的權(quán)值,輸出鄰接矩陣2最小生成樹是通過 Prim 算法完成的。Prim 里涉及到候選最短邊集，用數(shù)組 shortEdgen表示候選最短邊集，數(shù)組元素包括候選最短邊的的鄰接點（adjvex）和權(quán)值（lowcost）兩個域三、三、 概要設(shè)計概要設(shè)計第 5 頁 共 17 頁1. 鄰接矩陣的建立鄰接矩陣的建立1鄰接矩陣的初始化，頂點自己對自己的權(quán)值為 0，其余的權(quán)值均為 MaxWeight（自定義的無窮

9、大,999）AdjMatGraph:AdjMatGraph(const int sz)/sz 是頂點數(shù)，有參構(gòu)造函數(shù)for(int i=0;isz;i+)for(int j=0;jsz;j+)if(i=j)Edgeij=0;elseEdgeij=MaxWeight;/無窮大numOfEdges=0;2鄰接矩陣中點與點之間有弧的，則將兩個頂點之間的權(quán)值設(shè)為 weight 取代 MaxWeight（無窮大,999）void AdjMatGraph:InsertEdge(const int v1,const int v2,int weight)/插入弧，權(quán)為 weightif(v1Vertices.

10、ListSize()|v2Vertices.ListSize()cout參數(shù) v1,v2 有誤 2endl;exit(0);Edgev1v2=weight;Edgev2v1=weight;numOfEdges+;2. 圖的建立圖的建立struct RowColWeight/邊信息三元組int row;int col;int weight;void AdjMatCreateGraph(AdjMatGraph &G,DataType V,int n,RowColWeight E,int e)/用一個存儲邊權(quán)信息的三元組來生成圖第 6 頁 共 17 頁int i;for( i=0;in;i+

11、)G.InsertVertex(Vi);/填充頂點信息for(i=0;ie;i+)G.InsertEdge(Ei.row,Ei.col,Ei.weight);3. 求最小生成樹求最小生成樹struct shortEdgeint lowcost;int adjvex;void AdjMatGraph:Prim()int k,w,cost=0;for(int i=1;inumOfVertices();i+)shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0;shortEdge0.lowcost=0;for(int i=1;inumOfVertices();i

12、+)w=MaxWeight ;for(int j=1;jnumOfVertices();j+)if(shortEdgej.lowcost!=0 & shortEdgej.lowcostw)w=shortEdgej.lowcost;k=j;shortEdgek.lowcost=0;for(int j=1;jnumOfVertices();j+)if(Edgekj shortEdgej.lowcost)shortEdgej.lowcost=Edgekj;shortEdgej.adjvex=k;第 7 頁 共 17 頁cout最小生成樹為：endl;for(int i=1;inumOfVer

13、tices();i+)coutishortEdgei.adjvex-EdgeishortEdgei.adjvexendl;cost=cost+EdgeishortEdgei.adjvex;cout最小生成樹代價為：costendl;四、 數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計元素類型，結(jié)點類型class SeqListprivate:DataType dataMaxListSize;int size;public:SeqList();int ListSize()const;/返回元素的個數(shù) sizevoid Insert(const DataType & item,int pos);/在位置 pos

14、 插入元素 item;struct RowColWeight/邊信息三元組int row;int col;int weight;struct RowColWeight/邊信息三元組int row;int col;int weight;class AdjMatGraphprivate:SeqList Vertices;/用順序表存儲結(jié)點信息int EdgeMaxVerticesMaxVertices;/用數(shù)組存儲帶權(quán)或不帶權(quán)的邊int numOfEdges;/邊數(shù)shortEdge shortEdgeMaxSize;public:AdjMatGraph(const int sz=MaxVerti

15、ces);/有參構(gòu)造函數(shù),sz 為頂點數(shù)第 8 頁 共 17 頁int numOfVertices()/返回結(jié)點數(shù)目return Vertices.ListSize();int numOfEdge()/返回邊數(shù)return numOfEdges;void InsertVertex(const VerT &vertex);/插入結(jié)點 vertexvoid InsertEdge(const int v1,const int v2,int weight);/插入弧，權(quán)為 weightvoid printMGraph();void Prim();五、五、 算法設(shè)計算法設(shè)計1. 算法分析算法分析

16、根據(jù)用 Prim 算法求最小生成樹，設(shè) G=(V,E)是具有 n 個頂點的連通網(wǎng)，T=(U,TE)是 G 的最小生成樹，T 的初始狀態(tài)為 U=u0( u0V）),TE= ,重復(fù)執(zhí)行下述操作：在所有 uU,vV-U 的邊中找一條代價最小的邊（u，v）并入集合 TE,同時 v 并入 U,直至 U=V0,最后計算得到的最小生成樹的代價2. 算法實現(xiàn)算法實現(xiàn)void AdjMatGraph:Prim()int k,w,cost=0;for(int i=1;inumOfVertices();i+)shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0;shortEdg

17、e0.lowcost=0;for(int i=1;inumOfVertices();i+)w=MaxWeight ;for(int j=1;jnumOfVertices();j+)第 9 頁 共 17 頁if(shortEdgej.lowcost!=0 & shortEdgej.lowcostw)w=shortEdgej.lowcost;k=j;shortEdgek.lowcost=0;for(int j=1;jnumOfVertices();j+)if(Edgekj shortEdgej.lowcost)shortEdgej.lowcost=Edgekj;shortEdgej.adj

18、vex=k;cout最小生成樹為：最小生成樹為：endl;for(int i=1;inumOfVertices();i+)coutishortEdgei.adjvex-EdgeishortEdgei.adjvexendl;cost=cost+EdgeishortEdgei.adjvex;cout最小生成樹代價為：最小生成樹代價為：costendl;六、六、 程序測試與實現(xiàn)程序測試與實現(xiàn)1.主程序主程序void main()AdjMatGraph g;char a=A,B,C,D,E,F,G,H,I,J;RowColWeight rcw=0,4,1,0,1,2,4,5,3,0,5,4,1,5,5

19、,5,6,6,1,2,7,2,6,8,2,7,9,2,3,10,3,7,11,3,9,12,8,9,13,7,8,14,6,7,15;int n=10,e=15;/10 個頂點，個頂點，15 條邊條邊AdjMatCreateGraph(g,a,n,rcw,e);cout 當(dāng)前的頂點個數(shù)為：當(dāng)前的頂點個數(shù)為： g.numOfVertices() endl; cout 當(dāng)前的邊的條數(shù)為：當(dāng)前的邊的條數(shù)為： g.numOfEdge() endl;g.printMGraph();g.Prim();2.測試結(jié)果（測試結(jié)果（999 是我自己設(shè)置的無窮大）是我自己設(shè)置的無窮大）第 10 頁 共 17 頁七、

20、 調(diào)試分析調(diào)試分析1圖的鄰接矩陣是一個 n*n 的矩陣，所以其空間代價是 O(n2)2在求解最小生成樹的過程中，會不斷的讀取任意兩個頂點之間邊的權(quán)值，所以采用鄰接矩陣八、 遇到的問題及解決辦法遇到的問題及解決辦法在求解利用 Prim 求解最小生成樹的過程中，算法能夠看懂，但是利用 C+程序去實現(xiàn)，還是有問題的。最后反復(fù)看代碼，構(gòu)造了一個最短候選邊集，即數(shù)組 shortEdgen。九、九、 心得體會心得體會第 11 頁 共 17 頁本次課程設(shè)計用到了順序表的建立與插入，圖的鄰接矩陣存儲，最本次課程設(shè)計用到了順序表的建立與插入，圖的鄰接矩陣存儲，最終實現(xiàn)了求終實現(xiàn)了求 n 個個城市城市之間的相同公

21、路之間的最短距離，我主要學(xué)到之間的相同公路之間的最短距離，我主要學(xué)到了將實際問題轉(zhuǎn)換為自己所學(xué)到的知識，做到了學(xué)以致用。了將實際問題轉(zhuǎn)換為自己所學(xué)到的知識，做到了學(xué)以致用。十、十、 附錄（源代碼）附錄（源代碼）SeqList.h#includeusing namespace std;class SeqListprivate:DataType dataMaxListSize;int size;public:SeqList();int ListSize()const;/返回元素的個數(shù)返回元素的個數(shù) sizevoid Insert(const DataType & item,int pos)

22、;/在位置在位置 pos 插入元素插入元素 item;SeqList:SeqList()size=0;int SeqList:ListSize()constreturn size;void SeqList:Insert(const DataType & item,int pos)/在位置在位置 pos 插入元素插入元素 itemint i;if(size=MaxListSize)cout順序表已滿無法插入！順序表已滿無法插入！endl;exit(1);if(possize)/當(dāng)當(dāng) pos 等于等于 size 時表示插入在最后時表示插入在最后cout參數(shù)參數(shù) pos 越界出錯越界出錯!p

23、os;i-)datai=datai-1;datapos=item;/在在 pos 位置插入位置插入 itemsize+;/數(shù)據(jù)元素個數(shù)數(shù)據(jù)元素個數(shù) size 加加 1AdjMatGraphLib.hstruct RowColWeight/邊信息三元組邊信息三元組int row;int col;int weight;void AdjMatCreateGraph(AdjMatGraph &G,DataType V,int n,RowColWeight E,int e)/用一個存儲邊權(quán)信息的三元組來生成圖用一個存儲邊權(quán)信息的三元組來生成圖int i;for( i=0;in;i+)G.Inse

24、rtVertex(Vi);/填充頂點信息填充頂點信息for(i=0;ie;i+)G.InsertEdge(Ei.row,Ei.col,Ei.weight);AdjMatGraph.h#includeconst int MaxSize=100;struct shortEdgeint lowcost;int adjvex;class AdjMatGraphprivate:SeqList Vertices;/用順序表存儲結(jié)點信息用順序表存儲結(jié)點信息int EdgeMaxVerticesMaxVertices;/用數(shù)組存儲帶權(quán)或不帶權(quán)的邊用數(shù)組存儲帶權(quán)或不帶權(quán)的邊int numOfEdges;/邊數(shù)邊

25、數(shù)shortEdge shortEdgeMaxSize;public:AdjMatGraph(const int sz=MaxVertices);/有參構(gòu)造函數(shù)有參構(gòu)造函數(shù),sz 為頂點數(shù)為頂點數(shù)int numOfVertices()/返回結(jié)點數(shù)目返回結(jié)點數(shù)目return Vertices.ListSize();第 13 頁 共 17 頁int numOfEdge()/返回邊數(shù)返回邊數(shù)return numOfEdges;void InsertVertex(const VerT &vertex);/插入結(jié)點插入結(jié)點 vertexvoid InsertEdge(const int v1,c

26、onst int v2,int weight);/插入弧插入弧，權(quán)為，權(quán)為weightvoid printMGraph();void Prim();AdjMatGraph:AdjMatGraph(const int sz)/sz 是頂點數(shù)，有參構(gòu)造函數(shù)是頂點數(shù)，有參構(gòu)造函數(shù)for(int i=0;isz;i+)for(int j=0;jsz;j+)if(i=j)Edgeij=0;elseEdgeij=MaxWeight;/無窮大無窮大numOfEdges=0;void AdjMatGraph:InsertVertex(const VerT &vertex)/插入結(jié)點插入結(jié)點 verte

27、xVertices.Insert(vertex,Vertices.ListSize();void AdjMatGraph:InsertEdge(const int v1,const int v2,int weight)/插入弧插入弧，權(quán)為權(quán)為 weightif(v1Vertices.ListSize()|v2Vertices.ListSize()cout參數(shù)參數(shù) v1,v2 有誤有誤 2endl;exit(0);Edgev1v2=weight;Edgev2v1=weight;numOfEdges+;void AdjMatGraph:printMGraph()cout鄰接矩陣是：鄰接矩陣是：en

28、dl;for(int i=0;inumOfVertices();i+)第 14 頁 共 17 頁for(int j=0;jnumOfVertices();j+)coutsetw(10)Edgeij;coutendl;coutendl;void AdjMatGraph:Prim()int k,w,cost=0;for(int i=1;inumOfVertices();i+)shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0;shortEdge0.lowcost=0;for(int i=1;inumOfVertices();i+)w=MaxWeight ;for(int j=1;jnumOfVertices();j+)if(shortEdgej.lowcost!=0 &