离散数学-最小生成树

1、_实验五实验名称：得到最小生成树实验目的：1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力； 使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。2.掌握图论中的最小生成树及Prim 和 Kruskal算法等，进一步能用它们来解决实际问题。实验内容：输入一个图的权矩阵，得到该图的生成树，用Kruskal 算法的最小生成树，用 Prim 算法的最小生成树。精品资料_实验原理：Kruskal 算法假设 T中的边和顶点均涂成红色， 其余边为白色。 开始时 G中的边均为白色。1）将所有顶点涂成红色；2）在白色边中，挑选一条权最小的

2、边，使其与红色边不形成圈，将该白色边涂红；3）重复 2）直到有 n-1条红色边，这 n-1 条红色边便构成最小生成树T的边集合。Prim 算法假设 V是图中顶点的集合 ,E是图中边的集合 ,TE 为最小生成树中的边的集合,则 prim算法通过以下步骤可以得到最小生成树:1)初始化 :U=u 0,TE=f 。此步骤设立一个只有结点u 0 的结点集 U和一个空的边集 TE 作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化 ,直到得到最小生成树为止。精品资料_2)在所有 uU,vVU的边 (u,v) E中,找一条权最小的边 (u 0,v 0) ，将此边加进集合 TE 中，并将此

3、边的非 U中顶点加入 U中。此步骤的功能是在边集E中找一条边 ,要求这条边满足以下条件: 首先边的两个顶点要分别在顶点集合U和 V U中 ,其次边的权要最小。找到这条边以后 ,把这条边放到边集 TE 中,并把这条边上不在 U中的那个顶点加入到 U中。这一步骤在算法中应执行多次 ,每执行一次 ,集合TE 和U 都将发生变化 , 分别增加一条边和一个顶点,因此 ,TE 和 U是两个动态的集合 ,这一点在理解算法时要密切注意。3)如果 U=V, 则算法结束 ;否则重复步骤 2。可以把本步骤看成循环终止条件。我们可以算出当 U=V 时 ,步骤 2 共执行了 n 1 次( 设n 为图中顶点的数目),TE

4、 中也增加了 n1条边 ,这n1条边就是需要求出的最小生成树的边。实验结果：精品资料_精品资料_附：程序源代码：#include<iostream.h>#include<string.h>main()system("color 9c");cout<<" 请输入图的点数： n"int n;cin>>n;char c1='a'cout<<" 系统自动生成点为： n"int i,j,k;cout<<c1;for(i=1;i<n;i+)cout<

5、;<","<<(char)(c1+i);int ann;cout<<"n 请输入图的权矩阵： n"for(i=0;i<n;i+)for(j=0;j<n;j+)cin>>aij;cout<<"nn 此图的邻接矩阵为： n"for(i=0;i<n;i+)精品资料_cout<<(char)(c1+i)<<" "cout<<endl;for(i=0;i<n;i+)cout<<(char)(c1+i)

6、<<" "for(j=0;j<n;j+)if(aij)cout<<"1"<<" "elsecout<<"0"<<" "cout<<endl;int m=0;k=0;for(i=0;i<n;i+)for(j=0;j<n;j+)if(aij&&i<j)m+;int bm3;for(i=0;i<n;i+)/ 找出边和权for(j=0;j<n;j+)if(aij&&

7、i<j)精品资料_bk0=i;bk1=j;bk+2=aij;int t;for(i=0;i<m-1;i+)/ 排序for(j=i+1;j<m;j+)if(bi2>bj2)for(k=0;k<3;k+)t=bik;bik=bjk;bjk=t;for(i=0;i<m;i+)cout<<"("<<(char)(c1+bi0)<<","<<(char)(c1+bi1)<<","<<bi2<<")"cout

8、<<endl;int cn-13,dn;for(k=0;k<3;k+)c0k=b0k;d0=b00;d1=b01;精品资料_k=1;int k1=2,k2,k3,m1=0;for(i=1;i<m;i+)for(j=0;j<3;j+)ckj=bij;k+;k3=k1;for(k2=0;k2<k1;k2+)if(bi0=dk2)m1+;if(!m1)dk1+=bi0;elsem1=0;for(k2=0;k2<k1;k2+)if(bi1=dk2)m1+;if(!m1)dk1+=bi1;elsem1=0;精品资料_if(k>=k1)k-;k1=k3;if

9、(k=n)break;cout<<" 用 Kruskal 算法得到的最小生成树为：n"int count=0;for(i=0;i<n-2;i+)cout<<"("<<(char)(c1+ci0)<<","<<(char)(c1+ci1)<<"),"count+=ci2;cout<<"("<<(char)(c1+cn-10)<<","<<(char)(c

10、1+cn-11)<<")n"count+=cn-12;cout<<" 最小权和为： "<<count<<endl<<endl;for(k=0;k<3;k+)c0k=b0k;b02=0;d0=b00;d1=b01;k1=2;k2=0;k3=0,m1=1;精品资料_while(k1<=n)for(i=1;i<m;i+)if(bi2)for(j=0;j<k1;j+)if(bi0=dj)k2+;for(j=0;j<k1;j+)if(bi1=dj)k3+;if(k2&

11、&!k3)dk1+=bi1;for(k=0;k<3;k+)cm1k=bik;bi2=0;m1+;k2=0;goto h;else if(!k2&&k3)精品资料_dk1+=bi0;for(k=0;k<3;k+)cm1k=bik;bi2=0;m1+;k3=0;goto h;elsek2=k3=0;h:;cout<<" 用 Prim 算法得到的最小生成树为：n"count=0;for(i=0;i<n-2;i+)cout<<"("<<(char)(c1+ci0)<<","<<(char)(c1+ci1)<<"),"count+=ci2;精品资料_cout<<"("<<(char)(c1+cn-10)<<","<<(char)(c1