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

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

2、生成樹(shù)的代價(jià)。將該地區(qū)的城市用頂點(diǎn)表示，城市間的公路用樹(shù)的代價(jià)。將該地區(qū)的城市用頂點(diǎn)表示，城市間的公路用邊表示，公路的長(zhǎng)度作為邊的權(quán)值，最終這個(gè)問(wèn)題可以歸邊表示，公路的長(zhǎng)度作為邊的權(quán)值，最終這個(gè)問(wèn)題可以歸結(jié)為網(wǎng)圖中，求頂點(diǎn)結(jié)為網(wǎng)圖中，求頂點(diǎn) A A 到頂點(diǎn)到頂點(diǎn) B B 的所有路徑中，邊的權(quán)值的所有路徑中，邊的權(quán)值之和最少的那條路徑。之和最少的那條路徑。關(guān)鍵詞：關(guān)鍵詞：最小生成樹(shù)最小生成樹(shù) PrimPrim 算法算法 C+C+語(yǔ)言源程序語(yǔ)言源程序第 2 頁(yè) 共 17 頁(yè)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 頁(yè) 共 17 頁(yè)目 錄一、問(wèn)題描述一、問(wèn)題描述 .41.1 題目?jī)?nèi)容題目?jī)?nèi)容 .41.2 基本要求基本要求 .4二、需求分析二、需求分析 .4三、概要設(shè)計(jì)三、概要設(shè)計(jì) .43.1 鄰接矩陣的建立鄰接矩陣的建立.53.2 圖的建立圖的建立 .53.3 求最小生成樹(shù)求最小生成樹(shù).6四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì).7五、算法設(shè)計(jì)五、算法設(shè)計(jì) .85.1 算法分析算法分析 .85.2 算法實(shí)現(xiàn)算法實(shí)現(xiàn) .8六、程序測(cè)試與實(shí)現(xiàn)六、程序測(cè)試與實(shí)現(xiàn) .96.1 主程序主程序.

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

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

9、大,999）AdjMatGraph:AdjMatGraph(const int sz)/sz 是頂點(diǎn)數(shù)，有參構(gòu)造函數(shù)for(int i=0;isz;i+)for(int j=0;jsz;j+)if(i=j)Edgeij=0;elseEdgeij=MaxWeight;/無(wú)窮大numOfEdges=0;2鄰接矩陣中點(diǎn)與點(diǎn)之間有弧的，則將兩個(gè)頂點(diǎn)之間的權(quán)值設(shè)為 weight 取代 MaxWeight（無(wú)窮大,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)/用一個(gè)存儲(chǔ)邊權(quán)信息的三元組來(lái)生成圖第 6 頁(yè) 共 17 頁(yè)int i;for( i=0;in;i+

11、)G.InsertVertex(Vi);/填充頂點(diǎn)信息for(i=0;ie;i+)G.InsertEdge(Ei.row,Ei.col,Ei.weight);3. 求最小生成樹(shù)求最小生成樹(shù)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 頁(yè) 共 17 頁(yè)cout最小生成樹(shù)為：endl;for(int i=1;inumOfVer

13、tices();i+)coutishortEdgei.adjvex-EdgeishortEdgei.adjvexendl;cost=cost+EdgeishortEdgei.adjvex;cout最小生成樹(shù)代價(jià)為：costendl;四、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)元素類(lèi)型，結(jié)點(diǎn)類(lèi)型class SeqListprivate:DataType dataMaxListSize;int size;public:SeqList();int ListSize()const;/返回元素的個(gè)數(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;/用順序表存儲(chǔ)結(jié)點(diǎn)信息int EdgeMaxVerticesMaxVertices;/用數(shù)組存儲(chǔ)帶權(quán)或不帶權(quán)的邊int numOfEdges;/邊數(shù)shortEdge shortEdgeMaxSize;public:AdjMatGraph(const int sz=MaxVerti

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

16、根據(jù)用 Prim 算法求最小生成樹(shù)，設(shè) G=(V,E)是具有 n 個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是 G 的最小生成樹(shù)，T 的初始狀態(tài)為 U=u0( u0V）),TE= ,重復(fù)執(zhí)行下述操作：在所有 uU,vV-U 的邊中找一條代價(jià)最小的邊（u，v）并入集合 TE,同時(shí) v 并入 U,直至 U=V0,最后計(jì)算得到的最小生成樹(shù)的代價(jià)2. 算法實(shí)現(xiàn)算法實(shí)現(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 頁(yè) 共 17 頁(yè)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最小生成樹(shù)為：最小生成樹(shù)為：endl;for(int i=1;inumOfVertices();i+)coutishortEdgei.adjvex-EdgeishortEdgei.adjvexendl;cost=cost+EdgeishortEdgei.adjvex;cout最小生成樹(shù)代價(jià)為：最小生成樹(shù)代價(jià)為：costendl;六、六、 程序測(cè)試與實(shí)現(xiàn)程序測(cè)試與實(shí)現(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 個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，15 條邊條邊AdjMatCreateGraph(g,a,n,rcw,e);cout 當(dāng)前的頂點(diǎn)個(gè)數(shù)為：當(dāng)前的頂點(diǎn)個(gè)數(shù)為： g.numOfVertices() endl; cout 當(dāng)前的邊的條數(shù)為：當(dāng)前的邊的條數(shù)為： g.numOfEdge() endl;g.printMGraph();g.Prim();2.測(cè)試結(jié)果（測(cè)試結(jié)果（999 是我自己設(shè)置的無(wú)窮大）是我自己設(shè)置的無(wú)窮大）第 10 頁(yè) 共 17 頁(yè)七、

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

21、路之間的最短距離，我主要學(xué)到之間的相同公路之間的最短距離，我主要學(xué)到了將實(shí)際問(wèn)題轉(zhuǎn)換為自己所學(xué)到的知識(shí)，做到了學(xué)以致用。了將實(shí)際問(wèn)題轉(zhuǎn)換為自己所學(xué)到的知識(shí)，做到了學(xué)以致用。十、十、 附錄（源代碼）附錄（源代碼）SeqList.h#includeusing namespace std;class SeqListprivate:DataType dataMaxListSize;int size;public:SeqList();int ListSize()const;/返回元素的個(gè)數(shù)返回元素的個(gè)數(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順序表已滿(mǎn)無(wú)法插入！順序表已滿(mǎn)無(wú)法插入！endl;exit(1);if(possize)/當(dāng)當(dāng) pos 等于等于 size 時(shí)表示插入在最后時(shí)表示插入在最后cout參數(shù)參數(shù) pos 越界出錯(cuò)越界出錯(cuò)!p

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

24、rtVertex(Vi);/填充頂點(diǎn)信息填充頂點(diǎn)信息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;/用順序表存儲(chǔ)結(jié)點(diǎn)信息用順序表存儲(chǔ)結(jié)點(diǎn)信息int EdgeMaxVerticesMaxVertices;/用數(shù)組存儲(chǔ)帶權(quán)或不帶權(quán)的邊用數(shù)組存儲(chǔ)帶權(quán)或不帶權(quán)的邊int numOfEdges;/邊數(shù)邊

25、數(shù)shortEdge shortEdgeMaxSize;public:AdjMatGraph(const int sz=MaxVertices);/有參構(gòu)造函數(shù)有參構(gòu)造函數(shù),sz 為頂點(diǎn)數(shù)為頂點(diǎn)數(shù)int numOfVertices()/返回結(jié)點(diǎn)數(shù)目返回結(jié)點(diǎn)數(shù)目return Vertices.ListSize();第 13 頁(yè) 共 17 頁(yè)int numOfEdge()/返回邊數(shù)返回邊數(shù)return numOfEdges;void InsertVertex(const VerT &vertex);/插入結(jié)點(diǎn)插入結(jié)點(diǎn) 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 是頂點(diǎn)數(shù)，有參構(gòu)造函數(shù)是頂點(diǎn)數(shù)，有參構(gòu)造函數(shù)for(int i=0;isz;i+)for(int j=0;jsz;j+)if(i=j)Edgeij=0;elseEdgeij=MaxWeight;/無(wú)窮大無(wú)窮大numOfEdges=0;void AdjMatGraph:InsertVertex(const VerT &vertex)/插入結(jié)點(diǎn)插入結(jié)點(diǎn) 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 頁(yè) 共 17 頁(yè)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 &