离散数学-最小生成树

实验五 得到最小生成树实验五实验名称：得到最小生成树实验目的：1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。2.掌握图论中的最小生成树及Prim 和 Kruskal 算法等，进一步能用它们来解决实际问题。实验内容：输入一个图的权矩阵，得到该图的生成树，用Kruskal算法的最小生成树，用Prim算法的最小生成树。实验原理：Kruskal算法假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。 1）将所有顶点涂成红色； 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中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和VU中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。 3)如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n1次(设n为图中顶点的数目),TE中也增加了n1条边,这n1条边就是需要求出的最小生成树的边。实验结果：附：程序源代码：#include#include main() system(color 9c); coutn; char c1=a; cout系统自动生成点为：n; int i,j,k; coutc1; for(i=1;in;i+) cout,(char)(c1+i); int ann; coutn请输入图的权矩阵：n; for(i=0;in;i+) for(j=0;jaij; coutnn此图的邻接矩阵为：n ; for(i=0;in;i+) cout(char)(c1+i) ; coutendl; for(i=0;in;i+) cout(char)(c1+i) ; for(j=0;jn;j+) if(aij) cout1 ; else cout0 ; coutendl; int m=0;k=0; for(i=0;in;i+) for(j=0;jn;j+) if(aij&ij) m+; int bm3; for(i=0;in;i+) /找出边和权 for(j=0;jn;j+) if(aij&ij) bk0=i; bk1=j; bk+2=aij; int t; for(i=0;im-1;i+) /排序 for(j=i+1;jbj2) for(k=0;k3;k+) t=bik; bik=bjk; bjk=t; for(i=0;im;i+) cout(char)(c1+bi0),(char)(c1+bi1),bi2); coutendl; int cn-13,dn; for(k=0;k3;k+) c0k=b0k; d0=b00; d1=b01; k=1; int k1=2,k2,k3,m1=0; for(i=1;im;i+) for(j=0;j3;j+) ckj=bij; k+; k3=k1; for(k2=0;k2k1;k2+) if(bi0=dk2) m1+; if(!m1) dk1+=bi0; else m1=0; for(k2=0;k2=k1) k-; k1=k3; if(k=n)break; cout用Kruskal算法得到的最小生成树为：n; int count=0; for(i=0;in-2;i+) cout(char)(c1+ci0),(char)(c1+ci1),; count+=ci2; cout(char)(c1+cn-10),(char)(c1+cn-11)n; count+=cn-12; cout最小权和为：countendlendl; for(k=0;k3;k+) c0k=b0k; b02=0; d0=b00;d1=b01; k1=2;k2=0;k3=0,m1=1; while(k1=n) for(i=1;im;i+) if(bi2) for(j=0;jk1;j+) if(bi0=dj) k2+; for(j=0;jk1;j+) if(bi1=dj) k3+; if(k2&!k3) dk1+=bi1; for(k=0;k3;k+) cm1k=bik; bi2=0; m1+; k2=0; goto h; else if(!k2&k3) dk1+=bi0; for(k=0;k3;k+) cm1k=bik; bi2=0; m1+; k3=0; goto h; else k2=k3=0; h:; cout用Prim算法得到的最小生成树为：n; count=0; for(i=0;in-2;i+) cout(char)(c1+ci0),(