数据结构课程设计最小生成树问题

数据结构与算法课程设计报告课程设计题目：最小生成树问题专业班级：信息与计算科学1001班姓名：谢炜学号：100701114设计室号：理学院机房设计时间：2011-12-26批阅时间：指导教师：杜洪波成绩：一、摘要：随着社会经济的发展，人们的生活已经越来越离不开网络，网络成为人们社会生活的重要组成部分。我们希望拥有一个宽松的上网环境，以便更好的进行信息的交流，在此我们有必要提升我们的网络传播速度。从某种程度上来说网络传播速度代表着一个国家网络化程度的高低。为了解决网络传输速度的问题我们希望在各个城市之间多架设一些通信网络线路，以缓解网络不够流畅不够便捷的问题。而在城市之间架设网络线路受到资金因素等的限制，我们希望找到一条捷径这样我们即达到了连接了各个城市网络的目的又节省了建设成本。通过以上的分析我们得出解决此问题的关键在于找到一个短的路径完成网络的假设。在此我们想将各个城市抽象成为一个个节点，连接各个城市之间的网络作为连接各个节点的边。于是我们就将城市的空间分布抽象成为一个网络图，再将各条边的距离抽象成为各节点之间的权值。在原来的基础上建立一个带有权值的网络图。于是原有的问题就转化为找图的最小生成树问题。我们利用普利姆算法和卡鲁斯卡尔算法找到我们所需要的最小的生成树。二、问题分析在n个城市间建立通信网络，需架设n-1条路线。求解如何以最低的经济代价建设此通信网，这是一个最小生成树问题。我们可以利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市之间的距离。将城市之间的距离当做网中各点之间的权值。三、实现本程序需要解决的问题（1）如何选择存储结构去建立一个带权的网络；（2）如何在所选存储结构下输出这个带权网络；（3）如何实现普利姆算法的功能；（4）如何从每个顶点开始找到所有的最小生成树的顶点；（5）如何输出最小生成树的边及其权值此问题的关键就是利用普利姆算法，找到一个最小上的生成树，在一个就是输出我们所需要的信息，在此我们将各个城市看做是网中的各个顶点城市之间的距离看做是个顶点之间的权值。现在我们问题做如下的分析：这个问题主要在于普利姆算法的实现。我们将各个城市的空间分布抽象成一个带有权值的网络，这个权值就是任意两个城市之间，各个城市就看做是网络的各个顶点。我们建立的输入的数据格式为：首先提示输入带权的顶点数目，我定义为整形的数据型，然后输入每条边的信息，即边的两个顶点之间的权值，以十进制整数类型数据，这样我们就建立了一个带权的网络。问题的输出我是将我们所得到的最小生成树的路线输出出来。题目的要求就是我们在n个城市之间架设网络得到的最为经济的架设方法，我们进行以上的工作就是在找我们所需要的最小生成树，已解决我们的问题。四、算法思想普利姆算法求最小生成树的主要思想假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u,v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{E}）为N的最小生成树。对于最小生成树问题：最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个但是他们权值之和是相等的。五、程序设计流程图：六、模块划分（1）预处理#includestdio.h#definemaxvertexnum20#definemaxedgenum40typedefintadjmatrix[maxvertexnum][maxvertexnum];（2）定义一个储存节点信息的结构体structedgenode{intfrontvex;intrearvex;intweight;};typedefedgenodeadgeset[maxedgenum];（3）初始化的无向图，将每条边的权值赋值为无穷voidinsitadj(adjmatrix&GA){输入需要架设网络的城市的数目输入需要架设网络的各个城市之间的距离找到一个最小的生成树输出一个最小的生成树这个最小的生成树就是一个架设网络的最优解for(inti=1;imaxvertexnum;i++){for(intj=1;jmaxvertexnum;j++){GA[i][j]=20000;//将边的权值赋值为无穷//}}}（4）以各个城市为基础建立一个网络voidsetadj(adjmatrix&GA,intn)//建立网络{for(inti=1;i=n+1;i++){for(intj=i+1;jn+1;j++){printf(请输入第%d个城市到第%d个城市的距离：,i,j);scanf(%d,&GA[i][j]);}}for(i=1;i=n+1;i++){for(intj=i+1;jn+1;j++){GA[j][i]=GA[i][j];}}}（5）将建立的网络各个连接的节点赋上权值voidinsit(adgeset>,intn,adjmatrixGA){for(inti=1;in;i++){GT[i].frontvex=1;GT[i].rearvex=i+1;GT[i].weight=GA[1][i+1];}}（6）输出我们所找到的最小生成树voidfun(adjmatrixGA,adgeset>,intn){inti;for(i=1;in;i++){intmin=10000,m=i;for(intj=i;jn;j++){if(GT[j].weightmin){min=GT[j].weight;m=j;}}edgenodetemp=GT[i];GT[i]=GT[m];GT[m]=temp;intk=GT[m].rearvex;for(j=i;jn;j++){intt=GT[j].rearvex;intw=GA[k][t];if(wGT[j].weight){GT[j].weight=w;GT[j].frontvex=k;}}}}voiddisplay(adgesetGT,intn){for(inti=1;in;i++){printf(第%d个城市到第%d城市修建一条电缆!\n,GT[i].frontvex,GT[i].rearvex);}printf(这样修建可以使距离最短！);}（7）主函数intmain(){printf(请问您要在几个城市间建立网络？\n请在此输入：);intn;scanf(%d,&n);adgesetGT;adjmatrixGA;insitadj(GA);setadj(GA,n);insit(GT,n,GA);fun(GA,GT,n);display(GT,n);return0;}七、算法设计与分析选定存储形式要实现对于给定带权网络和顶点，运用普利姆基本算法思想求解所有的最小生成树的运算，在这里我们首先要明确所选用的数据结构，即采用何种数据结构来存储带权网络，这是必须首先解决的问题，我们采用图的邻接矩阵的存储方式来存储带权网络。我们在建立邻接矩阵的时候选用数组来分别存储每个节点的信息以及边的权值。八、源程序#includestdio.h#definemaxvertexnum20#definemaxedgenum40typedefintadjmatrix[maxvertexnum][maxvertexnum];structedgenode{intfrontvex;intrearvex;intweight;};typedefedgenodeadgeset[maxedgenum];//===============================================voidinsitadj(adjmatrix&GA);voidsetadj(adjmatrix&GA,intn);voidfun(adjmatrixGA,adgeset>,intn);voiddisplay(adgesetGT,intn);voidinsit(adgeset>,intn,adjmatrixGA);//=============================================voidinsit(adgeset>,intn,adjmatrixGA){for(inti=1;in;i++){GT[i].frontvex=1;GT[i].rearvex=i+1;GT[i].weight=GA[1][i+1];}}voidinsitadj(adjmatrix&GA){for(inti=1;imaxvertexnum;i++){for(intj=1;jmaxvertexnum;j++){GA[i][j]=20000;}}}voidsetadj(adjmatrix&GA,intn)//建立网络{for(inti=1;i=n+1;i++){for(intj=i+1;jn+1;j++){printf(请输入第%d个城市到第%d个城市的距离：,i,j);scanf(%d,&GA[i][j]);}}for(i=1;i=n+1;i++){for(intj=i+1;jn+1;j++){GA[j][i]=GA[i][j];}}}voidfun(adjmatrixGA,adgeset>,intn){inti;for(i=1;in;i++){intmin=10000,m=i;for(intj=i;jn;j++){if(GT[j].weightmin){min=GT[j].weight;m=j;}}edgenodetemp=GT[i];GT[i]=GT[m];GT[m]=temp;intk=GT[m].rearvex;for(j=i;jn;j++){intt=GT[j].rearvex;intw=GA[k][t];if(wGT[j].weight){GT[j].weight=w;GT[j].frontvex=k;}}}}voiddisplay(adgesetGT,intn){for(inti=1;in;i++){printf(第%d个城市到第%d城市修建一条电缆!\n,GT[i].frontvex,GT[i].rearvex);}printf(这样修建可以使距离最短！);}intmain(){printf(请问您要在几个城市间建立网络？\n请在此输入：);intn;scanf(%d,&n);adgesetGT;adjmatrixGA;insitadj(GA);setadj(GA,n);insit(GT,n,GA);fun(GA,GT,n);display(GT,n);return0;}九、算法实现（1）提示输入截图(2)输入各节点间的权（3）输出结果十、心得体会数据结构是学习计算机的一门重要的基础课，在学习数据结构之前我们学习了C语言在我们看来数据结构就是学习C语言的延续。我们知道像这种计算机类的课程必须配合着上机实际操作才能很好的学习他。但是我们平时在学习数据结构的过程中过少的参与到上机练习，在把精力放在了理论知识的学习上忽视了上机的重要性。在此次课程设计中我们深刻的体会到我们光靠学习理论只是不够的，因而我们很珍惜此次上机学习的机会。认真做好自己的程序。虽然我在刚刚接触到这些习题的时候会感到无所适从，不知道该从哪里下手。但是还是要细心认真的完成，在调试过程中虽然也会出现或多或少的错误，刚开始在遇到错误的时候非常焦躁，看到程序就会头大，但最终还是找到了状态，一步一步慢慢来，经过无数次的检查程序错误的原因后慢慢懂得了耐心是一个人成功的必然条件！在本次试验的学习中让我很清楚的认识了利用普利姆和克鲁斯卡尔算法求解最小生成树的算法思想，明白了最小生成树是怎么样形成的。我们将我们的城市的空间分布抽象为一个带有权值的网络为我们利用普利姆算法和克鲁斯卡尔算法提供了基础。在完成此次试验之后我感触很深。认识到数据结构这门课的重要性，在以后的学习计算机方面的课程时我们要注意理论与实践并行。多多