最小生成树数据结构实验报告

数据结构实验报告名称：最小生成树班级：122姓名：*****学号：***********指导老师：********2一、设计目的与任务1.1课程设计目的本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。1.2课程设计的任务问题描述:已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。二、设计方案2.1需求分析（1）建立一个图，其存储方式可以采用邻接矩阵形式或者邻接表；（2）利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树；（3）输入各城市的数目以及各个城市之间的距离。将城市之间的距离当做网中各点之间的权值。按顺序输出生成树中各条边以及它们的权值。2.2数据结构分析构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中3有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。弧v,w的意义或信息}2.3最小生成树的算法分析在该函数中主要有五段代码块，分别是主函数代码块、邻接矩阵定义模块代码、创建链接矩阵模块代码、最小生成树Prim算法及代价模块代码与最小生成树kruskal算法及代价模块代码，五段代码块分别有着不同的作用，共同满足了课题所需要实现的功能。2.4邻接矩阵定义模块代码typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];AdjMatrixarcs;intvexnum,arcnum;}MGraph_L;intlocalvex(MGraph_LG,charv){inti=0;while(G.vexs[i]!=v){++i;}returni;}用typedefstruct定义邻接矩阵，通过二维数组来存储邻接矩阵，并设定参数的最大值为20。2.5创建邻接矩阵模块代码4intcreatMGraph(MGraph&G){charv1,v2;inti,j,w;printf(建立邻接矩阵:\n);printf(请输入图G顶点（城市）和弧（边）的个数:);scanf(%d,&G.vexnum);scanf(%d,&G.arcnum);printf(输入所有顶点:);for(i=0;iG.vexnum;++i){cinG.vexs[i];}for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}printf(输入所有边及依附的顶点（城市）和权（距离）:\n);for(intk=0;kG.arcnum;k++){cinv1v2w;i=localvex(G,v1);5j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}ljjzprint(G);printf(图G邻接矩阵创建成功！\n);returnG.vexnum;}该语句是从键盘输入顶点数和边数，输入顶点和权值，通过循环语句的调用，最后调用creatMGraph_L（）创建连接矩阵。2.6最小生成树kruskal算法及代价模块代码voidMiniSpanTree(MGraphA*D)//生成最小生成树{inti,j,n,m,SUM=0;intk=1;intparent[M];edgeedges[M];for(i=1;iD-vexnum;i++){for(j=i+1;j=D-vexnum;j++){if(D-arc[i][j].adj==1){edges[k].begin=i;edges[k].end=j;edges[k].weight=D-arc[i][j].weight;k++;}}}sort(edges,D);for(i=1;i=D-arcnum;i++){6parent[i]=0;}printf(最小生成树为:\n);for(i=1;i=D-arcnum;i++)//核心部分{n=Find(parent,edges[i].begin);m=Find(parent,edges[i].end);if(n!=m){parent[n]=m;printf(%d,%d%d\n,)edges[i].begin,edges[i].end,edges[i].weight);SUM=SUM+edges[i].weight;}}cout最少生成树的代价:;coutSUM.该语句运用一系列的循环语句来实现的，利用前面的创建好的链接矩阵，通过各边权值的比较，最后调用MiniSpanTree()函数，实现最小生成树的生成，同时运用sum把最小生成树各边权值相加得到最小生成树的代价。四、调试分析。运行程序后出界面，运行结果如下图所示：7初界面图与邻接矩阵的生成prim算法求解8另一组数据：六、结论经过我不懈的努力我们终于完成了本次课程设计，9通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，我遇到了一些或大或小的问题，但是不论问题大小都会导致程序不能运行，这就要求我们要既有耐心又要细心，仔细推敲程序，从出现问题的地方起，并联系前后程序，逐个排查，直到最终搞清为止。我们本次做的是图的最小生成树问题。通过本次课程设计我们发现我们对于C语言和数据结构还有很多地方不知道，今后需要努力学习。七、程序部分源代码Typedefstruct{intadj;intweight;}AdjMatrix[MAX][MAX];Typedefstruct{djMatrixarc;intvexnum,arcnum;}MGraph10typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];AdjMatrixarcs;intvexnum,arcnum;}MGraph_L;intlocalvex(MGraph_LG,charv){inti=0;while(G.vexs[i]!=v){++i;}returni;}intcreatMGraph(MGraph&G){charv1,v2;inti,j,w;printf(建立邻接矩阵:\n);printf(请输入图G顶点（城市）和弧（边）的个数:);scanf(%d,&G.vexnum);scanf(%d,&G.arcnum);printf(输入所有顶点:);for(i=0;iG.vexnum;++i){cinG.vexs[i];}for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)11{G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}printf(输入所有边及依附的顶点（城市）和权（距离）:\n);for(intk=0;kG.arcnum;k++){cinv1v2w;i=localvex(G,v1);j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}ljjzprint(G);printf(图G邻接矩阵创建成功！\n);returnG.vexnum;voidMiniSpanTree(MGraphA*D)//生成最小生成树{inti,j,n,m,SUM=0;intk=1;intparent[M];edgeedges[M];for(i=1;iD-vexnum;i++){for(j=i+1;j=D-vexnum;j++){if(D-arc[i][j].adj==1){edges[k].begin=i;edges[k].end=j;12edges[k].weight=D-arc[i][j].weight;k++;}}}sort(edges,D);for(i=1;i=D-arcnum;i++){parent[i]=0;}printf(最小生成树为:\n);for(i=1;i=D-arcnum;i++)//核心部分{n=Find(parent,edges[i].begin);m=Find(parent,edges[i].end);if(n!=m){parent[n]=m;printf(%d,%d%d\n,)edges[i].begin,edges[i].end,edges[i].weight);SUM=SUM+edges[i].weight;}}cout最少生成树的代价:;coutSUM.