最小生成树问题

数据结构与算法课程设计报告课程设计题目：最小生成树问题专业班级：姓名：学号：设计室号：设计时间： 2011-12-26 批阅时间：指导教师：*绩：《数据结构与算法》课程设计报告姓名：学号：专业：一、课题：最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

存储结构采用多种。

求解算法多种。

问题分析:在n个城市间建立通信网络，需架设n-1条路线。

求解如何以最低的经济代价建设此通信网，这是一个最小生成树问题。

我们可以利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市之间的距离。

将城市之间的距离当做网中各点之间的权值。

二、功能、算法、体会描述：系统有一个主界面,是选择界面。

本系统一共有两种选择，克鲁斯卡尔算法求解和普利姆算法求解。

根据提醒，输入相应数据，选择你想要的求解方式。

第一种方式是克鲁斯卡尔算法。

输入你想要建立网络的城市数量，然后输入它们两两之间的建设成本，运行得到网络的建立方式。

第二种方式是普利姆算法，操作方法和第一种一致。

１．克鲁斯卡尔算法：基本思想：假设WN=（V, {E}）是一个含有N个顶点的连通网。

则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。

之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。

依次类推，直到森林中只有一棵树，也即子图中含有n-1条边为止。

在此系统中，N是你所需要输入的城市个数。

而每条边的权值就是你所输入的每两个城市之间的建设成本。

具体步骤：该算法的函数是main1( ) 。

先用struct edgenode{int frontvex;int rearvex;int weight;};typedef edgenode adgeset[maxedgenum];定义边结点，并定义一个此类结点的数组adgeset。

Main1中先用scanf("%d",&n)语句得到建立网络的城市个数n。

随后，通过insit1(adgeset&GT,int n)函数中的for( i=0;i<n-1;i++){for(int j=i+1;j<n;j++){int x,y;x=i+1;y=j+1;printf("请输入第%d个城市到第%d个城市的建设成本\n",x,y);scanf("%d",&a);GT[k].frontvex=i;GT[k].rearvex=j;GT[k].weight=a;k++;}}循环语句来得到每两个城市间的建设成本。

而后，通过for(i=0;i<k-1;i++){int min=20000,m=i;for(int j=i;j<k;j++){if(GT[j].weight<min){min=GT[j].weight;m=j;}}edgenode temp=GT[i];GT[i]=GT[m];GT[m]=temp;}}来寻找两边还没有顶点的权值最小边。

紧接着，用void fun1(adgeset&GE,adgeset&GT,int n)函数来得到我们所要的建设成本。

最后通过display1(GE,n);函数来输出该算法所求得的结果，即告知n-1条边该分别建立在哪几对城市之间。

２．普利姆算法：基本思想：假设WN=(V,{E})是一个含有n个顶点的连通网，TV是WN上最小生成树中顶点的集合，TE是最小生成树中边的集合。

显然，在算法执行结束时，TV=V，而TE是E的一个子集。

在算法开始执行时，TE为空集，TV中只有一个顶点，因此，按普利姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有n-1条边为止。

在此系统中，N是你所需要输入的城市个数。

而每条边的权值就是你所输入的每两个城市之间的建设成本。

具体步骤：该算法的函数是pum( ) 。

先用struct edgenode{int frontvex;int rearvex;int weight;};typedef edgenode adgeset[maxedgenum];定义边结点，并定义一个此类结点的数组adgeset。

Pum（）中先用scanf("%d",&n)语句得到建立网络的城市个数n。

接着，用函数void insitadj2(adjmatrix &GA){for(int i=0;i<maxvertexnum;i++){for(int j=0;j<maxvertexnum;j++){GA[i][j]=20000;}}}来给矩阵里的元素全赋初值无穷大。

然后通过void setadj2(adjmatrix &GA,int n)函数中的for(int i=0;i<=n;i++){for(int j=i+1;j<n;j++){int y,w;y=i+1;w=j+1;printf("请输入第%d个城市到第%d个城市的建设成本：",y,w);scanf("%d",&GA[i][j]);}}循环来得到每两个城市间的建设成本。

得到成本后，用fun2()函数来得到最小生成树。

最后通过Display2来输出我们需要的建设方案。

程序结构：Main()函数包括2大函数，图形显示如下：Main （）Kul ( )Pum ( )Main( )函数中kul( )函数也包括3个函数，图形显示如下Insit1( )Kul ( )display1 ( )Fun1 ( )main()函数中的pum ( )函数也包括5个函数，图形显示如下：数据显示：这儿只显示一下“根据克鲁斯卡尔算法求解”功能，其它功能用户可以自行调试查看 pum ( ) Insit2( )Display2 ( )Fun2 ( )setadj2 ( )insitadj2( )请您输入选择:1请输入您所要建立网络的城市个数：4请输入您所要建立网络的城市两两之间的建设成本：系统将根据克鲁斯卡尔算法进行求解，得到建设成本最低的建设方案：心得体会：通过此次课程设计，我更深刻地理解了最小生成树问题，知道如何在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

并且用了多种求解方式。

数据结构是学习计算机的一门重要的基础课，在学习数据结构之前我们学习了C语言在我们看来数据结构就是学习C语言的延续。

这几天的课程设计让我充分地体会到了上机实践对于计算机编程的重要性。

其实在于计算机语言这类课程看重的就是上机的实际操作，不满足于基本理论的学习。

上机操作才能让我们更加好的掌握我们所要学习的计算机语言知识。

只顾学习理论是远远不够的。

实践中可以发现许许多多的问题，然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。

此外，也让我更加明白编程是要解决现实问题的。

只有拥有把现实问题理论化的能力，才是编程真正需要达到的境界。

源程序：#include<stdio.h>#include<malloc.h>const int maxvertexnum=20;const int maxedgenum=40;typedef int adjmatrix[maxvertexnum][maxvertexnum];struct edgenode{int frontvex;int rearvex;int weight;};typedef edgenode adgeset[maxedgenum];//=============================================== void fun1(adgeset&GE,adgeset&GT,int n);void display1(adgeset GT,int n);void insit1(adgeset &GT,int n);int kul();//============================================= void insit1(adgeset&GT,int n){int k=0,a;int i;for( i=0;i<n-1;i++){for(int j=i+1;j<n;j++){int x,y;x=i+1;y=j+1;printf("请输入第%d个城市到第%d个城市的建设成本\n",x,y);scanf("%d",&a);GT[k].frontvex=i;GT[k].rearvex=j;GT[k].weight=a;k++;}}for(i=0;i<k-1;i++){int min=20000,m=i;for(int j=i;j<k;j++){if(GT[j].weight<min){min=GT[j].weight;m=j;}}edgenode temp=GT[i];GT[i]=GT[m];GT[m]=temp;}}void fun1(adgeset&GE,adgeset&GT,int n){int i,j;int**s=(int**) malloc (sizeof(int*));for(i=0;i<n;i++)s[i]=(int *) malloc (sizeof(int)); for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j)s[i][j]=1;else s[i][j]=0;}}int k=1;int d=0;int m1,m2;while(k<n){for(i=0;i<n;i++){if(s[i][GT[d].frontvex]==1)m1=i;if(s[i][GT[d].rearvex]==1)m2=i;}if(m1!=m2){GE[k-1]=GT[d];k++;for(j=0;j<n;j++){s[m1][j]=s[m2][j]||s[m1][j];s[m1][j]=0;}}d++;}//for(i=0;i<n;i++) free(s[i]);//free(s);}void display1(adgeset GT,int n){for(int i=0;i<n-1;i++){int x,y;x= GT[i].frontvex+1;y= GT[i].rearvex+1;printf("第%d个城市到第%d个城市修建一条电缆!\n",x,y);}printf("这样修建可以使建设成本最低！\n");}int kul(){printf("你要在几个城市间建设网络？请输入：\n");int n;scanf("%d",&n);adgeset GT,GE;insit1(GT,n);fun1(GE,GT,n);display1(GE,n);return 0;}//=============================================== void insitadj2(adjmatrix &GA);void setadj2(adjmatrix &GA,int n);void fun2(adjmatrix GA,adgeset &GT,int n);void display2(adgeset GT,int n);void insit2(adgeset &GT,int n,adjmatrix GA);int pum();//============================================= void insit2(adgeset&GT,int n,adjmatrix GA){for(int i=0;i<n-1;i++){GT[i].frontvex=0;GT[i].rearvex=i+1;GT[i].weight=GA[0][i+1];}}void insitadj2(adjmatrix &GA){for(int i=0;i<maxvertexnum;i++){for(int j=0;j<maxvertexnum;j++){GA[i][j]=20000;}}}void setadj2(adjmatrix &GA,int n){for(int i=0;i<=n;i++){for(int j=i+1;j<n;j++){int y,w;y=i+1;w=j+1;printf("请输入第%d个城市到第%d个城市的建设成本：",y,w);scanf("%d",&GA[i][j]);}}for(i=0;i<=n;i++){for(int j=i+1;j<n;j++){GA[j][i]=GA[i][j];}}}void fun2(adjmatrix GA,adgeset&GT,int n){ int i;for(i=0;i<n-1;i++){int min=10000,m=i;for(int j=i;j<n-1;j++){if(GT[j].weight<min){min=GT[j].weight;m=j;}}edgenode temp=GT[i];GT[i]=GT[m];GT[m]=temp;int k=GT[m].rearvex;for(j=i;j<n-1;j++){int t=GT[j].rearvex;int w=GA[k][t];if(w<GT[j].weight){GT[j].weight=w;GT[j].frontvex=k;}}}}void display2(adgeset GT,int n){for(int i=0;i<n-1;i++){ int e,r;e=GT[i].frontvex+1;r=GT[i].rearvex+1;printf("第%d个城市到第%d个城市修建一条电缆！\n",e,r);}printf("这样修建可以使建设成本最低！");}int pum(){printf("你要在几个城市间建设网络？\n请在此输入：");int n;scanf("%d",&n);adgeset GT;adjmatrix GA;insitadj2(GA);setadj2(GA,n);insit2(GT,n,GA);fun2(GA,GT,n);display2(GT,n);return 0;}void main(){printf(" \n\n\n\n\n\n ___________________________________________________________________\n 请选择您要的操作方式：\n ");printf("\n\n\n 1.根据克鲁斯卡尔算法求解。