构造可以使n个城市连接的最小生成树Word格式.docx

1、本次课程设计的要求是给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。将该地区的城市用顶点表示，城市间的公路用边表示，公路的长度作为边的权值，最终这个问题可以归结为网图中，求顶点A到顶点B的所有路径中，边的权值之和最少的那条路径。关键词：最小生成树 Prim算法 C+语言源程序AbstractThe curriculum design requirements is given a region n city, the distance between the net with the Prim algorithm to establish mini

2、mum spanning tree, and calculated the price of minimum spanning tree. Cities in the region with vertex said, between highway in the city edge, said the length of the road as the edge of the right values, finally the problem can be summed up in network diagram, and all the paths of vertex A to B, the

3、 edge of the weights of the sum of the minimum path.Keywords:minimum spanning treePrim algorithm C+ language source program一、问题描述 4题目内容 4基本要求 4二、需求分析 4三、概要设计 4邻接矩阵的建立 5图的建立 5求最小生成树 6四、数据结构设计 7五、算法设计 8算法分析 8算法实现 8六、程序测试与实现 9主程序 9测试结果 10七、调试分析 10八、遇到的问题及解决办法 10九、心得体会 10十、附录 11一、问题描述1题目内容：给定一个地区的n个城市间的

4、距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。2基本要求：a）城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。（要求至少10个城市，15条边）b）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。二、需求分析本程序的功能包括图的建立（采用邻接矩阵存储）和求最小生成树。1图的建立涉及到顶点数组datan和邻接矩阵Edgenn，顶点数组运用顺序表完成，操作有：顶点的插入即顺序表的插入；邻接矩阵的建立，操作有：插入弧和对应的权值,输出邻接矩阵2最小生成树是通过Prim算法完成的。Prim里涉及到候选最短边集，用数组sh

5、ortEdgen表示候选最短边集，数组元素包括候选最短边的的邻接点（adjvex）和权值（lowcost）两个域三、概要设计1.邻接矩阵的建立1邻接矩阵的初始化，顶点自己对自己的权值为0，其余的权值均为MaxWeight（自定义的无穷大,999）AdjMatGraph:AdjMatGraph（const int sz）ow,Ei.col,Ei.weight）;2.求最小生成树struct shortEdge int lowcost; int adjvex;void AdjMatGraph:Prim（） int k,w,cost=0; for（int i=1;inumOfVertices（）;i

6、+） shortEdgei.lowcost=Edge0i; shortEdgei.adjvex=0; shortEdge0.lowcost=0; w=MaxWeight ; for（int j=1;jj+） if（shortEdgej.lowcost!=0 & shortEdgej.lowcostw） w=shortEdgej.lowcost; k=j; shortEdgek.lowcost=0; if（Edgekj shortEdgej.lowcost） shortEdgej.lowcost=Edgekj; shortEdgej.adjvex=k; cout最小生成树为：endl; cout

7、shortEdgei.adjvex-EdgeishortEdgei.adjvex cost=cost+EdgeishortEdgei.adjvex;最小生成树代价为：cost四、数据结构设计元素类型，结点类型class SeqListprivate: DataType dataMaxListSize; int size;public: SeqList（）; int ListSize（）const;owcost=Edge0i;五、程序测试与实现1.主程序void main（） AdjMatGraph g; char a=A,BCDEFGHIJ RowColWeight rcw=0,4,1,0,1

8、,2,4,5,3,0,5,4,1,5,5,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;ow,Ei.col,Ei.weight）;#includeconst int MaxSize=100;class AdjMatGraph SeqList Vertices;iostreamtypedef char DataType;const int MaxListSize=100;const int SeqQMaxSize=100;#includeconst int MaxVertices=100;const int MaxWeight=999;typedef char VerT;using namespace std;/10个顶点，15条边 AdjMatCreateGraph（g,a,n,rcw,e）; cout 当前的顶点个数为： （） endl;当前的边的条数为： （）;