数据结构课程设计最小通信网

数据结构课程设计最小通信网需求分析要在n个城市间建立通信网，已知各个城市间的距离，建立的通信线路要使得这n个城市连通，而且建立的通信网络代价最小（最短）。输入:n个城市的距离关系图，即图的顶点和边上的权值输出:含n个城市顶点的最小生成树中的边和代价功能:建立图的最小生成树（4）测试数据:见右图概要设计数据结构:用图来描述n个城市间的关系，顶点为城市，边上的权值为两个城市的代价。用邻接矩阵来存储图.使用算法的思想：这里用prim算法来实现求最小生成树，假设G=（V，E）为待求图，其中V为图中所有顶点的集合，E为带权图中多有带权边的集合。设置两个新的集合U和TE，其中集合U用于存放G的最小生成树中的顶点，集合TE存放G的最小生成树的边。令集合U的初值为U{u1}（假设构造最小生成树时，从顶点u0出发），集合TE的初值为TE={}。Prim算法的思想是，从所有u属于U，v属于V-U的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合TE中，如此不断重复直到U=V时，最小生成树构造完毕，这时集合TE中包含了最小生成树的所有边。详细设计数据结构详细设计:图的邻接矩阵描述：此处用32767代表表头为顶点，矩阵的内容点—权值—点2.算法详细设计：在prim算法中，应当考虑如何有效的找出满足条件的i∈U，j∈V-U,且权c[i][j]最小的边（i,j）.实现这个目的的较简单的办法是设置两个一维数组closest和lowcost。Lowsest[j]中存储i∈U，j∈V-U且权值最小的边（i,j）的权值c[i][j]，而closest[j]中存储的是最小边（i,j）的另一个断点i。在prim算法执行过程中，先找出V-U中lowcost值最小的顶点j，然后根据数组closest选取边（j,closest[j]），最后将j添加到U中，并对其他closest和lowcost作必要的修改，下面是对该算法的详细说明。变量说明：Lowcost[i]若为初始的时候，表示（u0,i）的权值Closest[j]若为初始的时候，表示顶点j的另一端顶点，（Closest[j],j）2.对算法的语言描述：intPrim(GraphG,intu){ lowcost[MAXN],closest[MAXN];/*初始两个数组，值都为无穷大 for(该图中所有顶点的个数)/*初始U集合和V-U集合 {closest[i]=u0;/*初始时U中只有u0点*/ lowcost[i]=G.Arcs[u0][i];/*U中顶点到V-U中顶点的代价*/ }/*寻找U集合中的顶点到V-U集合中最小权值的顶点，并逐步更改U集合 for(该图中所有顶点个数) { /*设置一个变量为min，此值初始时为无穷大;for(顶点个数以j计数) if(j到u0得权值不为0且小于无穷大) { 用j到u0得权值替换掉min的值; 把j这个点记录到k中 }/*更改U集合和V-U集合 把找到的U集合中顶点到V-U集合中最小权值设置为0，这样就类似的把该顶点加到U中 for(顶点个数) if(j到k得权值不为0切小于点j到u0得权值) { 把j到u0得权值赋值给lowcost[j]中 把k赋值给closest[j] } }}调试分析调试过程中遇到的问题：在调试过程中，创建图的时候没有把顶点从0开始，结果总是导致输出不正确；还有，我设置的创建的图的格式应该：顶点，顶点，权值，中间是以逗号隔开的，在一开始我是用空格隔开，总是导致错误，这些错误都是可以避免的算法的时空分析：算法共有四个for循环，第一个循环次数为n,第二个循环次数为n-1（这是由于初始时已经把u0放入到U集合当中），第三个位n，第四个为n，并且第二个和第三个，四个循环嵌套，所以循环次数的平方数量级。所以时间复杂度O(n2)。算法中用到了两个辅助一维数组closese和lowcost，数组的大小为n，即图的顶点个数，所以算法的空间复杂度为O（n）.使用说明和测试结果使用说明：(1).创建图的时候，顶点要从0开始，有序连接的建立，并且要以逗号隔开，例如：顶点1，顶点2，权值（回车）；这样一条边就建立了。(2).测试数据：测试结果：心得体会虽然在课上已经学习了prim算法，但只知道手动的算法，具体用语言来实现对我来说还是有困难的，参考了教材上的程序，