最小生成树问题

1、数据结构与算法课程设计报告课程设计题目t小生成树问题专业班级:姓 名:学 号:设计室号：设计时间：2011-12-26批阅时间:绩:指导教师:绩:数据结构与算法课程设计报告姓名： 学号： 专业：一、课题：最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储 结构采用多种。求解算法多种。问题分析：在n个城市间建立通信网络，需架设n-1条路线。求解如何以最低的经济代 价建设此通信网，这是一个最小生成树问题。我们可以利用普利姆算法或者克鲁 斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市之间的距离。 将城市之间的距离当做网中各点之间的权值。二、功能、算

2、法、体会描述：系统有一个主界面，是选择界面。本系统一共有两种选择，克鲁斯卡尔算法 求解和普利姆算法求解。根据提醒，输入相应数据，选择你想要的求解方式。第 一种方式是克鲁斯卡尔算法。输入你想要建立网络的城市数量，然后输入它们两 两之间的建设成本，运行得到网络的建立方式。第二种方式是普利姆算法，操作 方法和第一种一致。1.克鲁斯卡尔算法：基本思想：假设WN= (V, E)是一个含有N个顶点的连通网。则按照克鲁斯卡 尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集 为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它 是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值

3、最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也 就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条 边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最 小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1条边为止。在此系统中，N是你所需要输入的城市个数。而每条 边的权值就是你所输入的每两个城市之间的建设成本。具体步骤：该算法的函数是main1()。先用 struct edgenode(int frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum;定义边结点，并定义一

4、个此类结点的数组 adgeset。Main1中先用 scanf(%d,&n)语句得到建立网络的城市个数n。随后，通过 insit1(adgeset>,int n)函数中的for( i=0;in-1;i+)(for(int j=i+1;jn;j+)(int x,y;x=i+1;y=j+1;printf(请输入第d个城市到第d个城市的建设成本n,x,y); scanf(%d,&a);GTk.frontvex=i;GTk.rearvex=j;GTk.weight=a;k+;循环语句来得到每两个城市间的建设成本。而后，通过for(i=0;ik-1;i+)(int min=20000,m=i;for

5、(int j=i;jk;j+)(if(GTj.weightmin)(min=GTj.weight;m=j;edgenode temp=GTi;GTi=GTm;GTm=temp;来寻找两边还没有顶点的权值最小边。紧接着，用 void fUn1(adgeset&GE,adgeset>,int n)函数来得到我们 所要的建设成本。最后通过display1(GE,n);函数来输出该算法所求 得的结果，即告知n-1条边该分别建立在哪几对城市之间。2.普利姆算法：基本思想：假设WN=(V,E)是一个含有n个顶点的连通网，TV是WN上最小 生成树中顶点的集合，TE是最小生成树中边的集合。显然，在算法 执

6、行结束时，TV=V，而TE是E的一个子集。在算法开始执行时， TE为空集，TV中只有一个顶点，因此，按普利姆算法构造最小生成 树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点 尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树 上，直至生成树中含有n-1条边为止。在此系统中，N是你所需要输 入的城市个数。而每条边的权值就是你所输入的每两个城市之间的建 设成本。具体步骤：该算法的函数是pum()。先用 struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum;定

7、义边结点，并定义一个此类结点的数组adgeset。Pum ()中先用scanf(%d,&n)语句得到建立网络的城市个数n。接着，用函数 void insitadj2(adjmatrix &GA)for(int i=0;imaxvertexnum;i+)for(int j=0;jmaxvertexnum;j+)GAij=20000;来给矩阵里的元素全赋初值无穷大。然后通过 void setadj2(adjmatrix &GA,int n)函数中的 for(int i=0;i=n;i+)for(int j=i+1;jn;j+)int y,w;y=i+1;w=j+1;printf(请输入第%d个城市

8、到第%d个城市的建设成本：,y,w)scanf(%d”,&GAij)循环来得到每两个城市间的建设成本。得到成本后，用fun2()函数来得到最小生成树。最后通过Display2来 输出我们需要的建设方案。程序结构:Main()函数包括2大函数，图形显示如下:Main()函数中kul()函数也包括3个函数，图形显示如下main()函数中的pum ()函数也包括5个函数，图形显示如下:数据显示：这儿只显示一下“根据克鲁斯卡尔算法求解”功能，其它功能用户可以自行调试 查看请您输入选择:1请输入您所要建立网络的城市个数：4请输入您所要建立网络的城市两两之间的建设成本:k要在凡-个城市间建没网努？请输入：

9、4熠输入第1个城市到第行城市的建设成本 请输入第1个城市到第3个城市的建设成本 请输入第1个城市到第4个城市的建设成本 错输入第N个城市到第3个城市的建设成本 34清输入第2个城市到第斗个城市的建设成本 25清箱入第3个城市到第牛个城市的建设成本 65系统将根据克鲁斯卡尔算法进行求解，得到建设成本最低的建设方案:第1个城市到第2个城市修建一条电缆! 第1个城市到第3个城市修建一条电缆? 第2个城市到第4个城市修建一条电缆 这样修建可以便建设成本最低！ Press any key to continue心得体会:通过此次课程设计，我更深刻地理解了最小生成树问题，知道 如何在n个城市之间建设网络，

10、只需保证连通即可，求最经济的架设 方法。并且用了多种求解方式。数据结构是学习计算机的一门重要的基础课，在学习数据结构之 前我们学习了 C语言在我们看来数据结构就是学习C语言的延续。 这几天的课程设计让 我充分地体会到了上机实践对于计算机编程 的重要性。其实在于计算机语言这类课程看重的就是上机的实际操作， 不满足于基本理论的学习。上机操作才能让我们更加好的掌握我们所 要学习的计算机语言知识。只顾学习理论是远远不够的。实践中可以发现许许多多的问题， 然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的 提升。此外，也让我更加明白编程是要解决现实问题的。只有拥有把 现实问题理论化的能力，才是

11、编程真正需要达到的境界。源程序：#include#include const int maxvertexnum=20;const int maxedgenum=40;typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenode(int frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum;/=void fun1(adgeset&GE,adgeset>,int n);void display1(adgeset GT,int n);void insit1

12、(adgeset >,int n);int kul();/=void insit1(adgeset>,int n)(int k=0,a;int i;for( i=0;in-1;i+)(for(int j=i+1;jn;j+)(int x,y;x=i+1;y=j+1;printf(请输入第d个城市到第d个城市的建设成本n,x,y);scanf(%d,&a);GTk.frontvex=i;GTk.rearvex=j;GTk.weight=a;k+;for(i=0;ik-1;i+)(int min=20000,m=i;for(int j=i;jk;j+)(if(GTj.weightmin)(

13、min=GTj.weight;m=j;edgenode temp=GTi;GTi=GTm;GTm=temp;void fun1(adgeset&GE,adgeset>,int n)(int i,j;int*s=(int*) malloc (sizeof(int*);for(i=0;in;i+)si=(int *) malloc (sizeof(int);for(i=0;in;i+)(for(j=0;jn;j+)(if(i=j)sij=1;else sij=0;int k=1;int d=0;int m1,m2;while(kn)(for(i=0;in;i+)(if(siGTd.frontv

14、ex=1)m1=i;if(siGTd.rearvex=1)m2=i;if(m1!=m2)(GEk-1=GTd;k+;for(j=0;jn;j+)(sm1j=sm2j|sm1j;sm1j=0;d+;/for(i=0;in;i+) free(si);/free(s);void display1(adgeset GT,int n)for(int i=0;in-1;i+)(int x,y;x= GTi.frontvex+1;y= GTi.rearvex+1;printf(第d个城市到第d个城市修建一条电缆!n,x,y);printf(这样修建可以使建设成本最低！ n);int kul()(printf

15、(你要在几个城市间建设网络？请输入：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 >,int n);void display2(adgeset GT,int n);void insit2(adgeset >,int n,adjmatrix GA);int pum();/

16、=void insit2(adgeset>,int n,adjmatrix GA)(for(int i=0;in-1;i+)(GTi.frontvex=0;GTi.rearvex=i+1;GTi.weight=GA0i+1;void insitadj2(adjmatrix &GA)for(int i=0;imaxvertexnum;i+)for(int j=0;jmaxvertexnum;j+)GAij=20000;void setadj2(adjmatrix &GA,int n)(fOr(int i=0;i=n;i+)(for(int j=i+1;jn;j+)(int y,w;y=i+1

17、;w=j+1;printf(请输入第d个城市到第d个城市的建设成本：,y,w);scanf(%d”,&GAij);for(i=0;i=n;i+)(for(int j=i+1;jn;j+)(GAji=GAij;void fun2(adjmatrix GA,adgeset>,int n)( int i;for(i=0;in-1;i+)(int min=10000,m=i;for(int j=i;jn-1;j+)(if(GTj.weightmin)(min=GTj.weight;m=j;edgenode temp=GTi;GTi=GTm;GTm=temp;int k=GTm.rearvex;for(j=i;jn-1;j+)int t=GTj.rearvex;int w=GAkt;if(wGTj.weight)(GTj.weight=w;GTj.frontvex=k;void display2(adgeset GT,int n)(for(int i=0;in-1;i+)( int e,r;e=GTi.frontvex+1;r=GTi.rearvex+1;printf(第d个城市到第d个城市修建一条电缆！ n,e,r);printf(这样修建可以使建设成本最低！)；int pum()(printf(-你要在几个城市间建设网络？ n请在此输入：，int n;scanf(%d,&n);