实验五实验名称：得到最小生成树实验目的：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)在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。

此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U 中,其次边的权要最小。

找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。

这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。

3)如果U=V,则算法结束;否则重复步骤2。

可以把本步骤看成循环终止条件。

我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。

附：程序源代码：#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<<","<<(char)(c1+i);int a[n][n];cout<<"\n请输入图的权矩阵：\n";for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>a[i][j];cout<<"\n\n此图的邻接矩阵为：\n ";for(i=0;i<n;i++)cout<<(char)(c1+i)<<" ";cout<<endl;for(i=0;i<n;i++){cout<<(char)(c1+i)<<" ";for(j=0;j<n;j++)if(a[i][j])cout<<"1"<<" ";elsecout<<"0"<<" ";cout<<endl;}int m=0;k=0;for(i=0;i<n;i++)for(j=0;j<n;j++)if(a[i][j]&&i<j)m++;int b[m][3];for(i=0;i<n;i++) //找出边和权 for(j=0;j<n;j++)if(a[i][j]&&i<j){b[k][0]=i;b[k][1]=j;b[k++][2]=a[i][j];}int t;for(i=0;i<m-1;i++) //排序for(j=i+1;j<m;j++)if(b[i][2]>b[j][2])for(k=0;k<3;k++){t=b[i][k];b[i][k]=b[j][k];b[j][k]=t;}for(i=0;i<m;i++)cout<<"("<<(char)(c1+b[i][0])<<","<<(char)(c1+b[i][1])<<","<<b[i][2]< <")";cout<<endl;int c[n-1][3],d[n];for(k=0;k<3;k++)c[0][k]=b[0][k];d[0]=b[0][0];d[1]=b[0][1];k=1;int k1=2,k2,k3,m1=0;for(i=1;i<m;i++){for(j=0;j<3;j++)c[k][j]=b[i][j];k++;k3=k1;for(k2=0;k2<k1;k2++)if(b[i][0]==d[k2])m1++;if(!m1)d[k1++]=b[i][0];elsem1=0;for(k2=0;k2<k1;k2++)if(b[i][1]==d[k2])m1++;if(!m1)d[k1++]=b[i][1];elsem1=0;if(k>=k1){k--;k1=k3;}if(k==n)break;}cout<<"用Kruskal算法得到的最小生成树为：\n{";int count=0;for(i=0;i<n-2;i++){cout<<"("<<(char)(c1+c[i][0])<<","<<(char)(c1+c[i][1])<<"),";count+=c[i][2];}cout<<"("<<(char)(c1+c[n-1][0])<<","<<(char)(c1+c[n-1][1])<<")}\n"; count+=c[n-1][2];cout<<"最小权和为："<<count<<endl<<endl;for(k=0;k<3;k++)c[0][k]=b[0][k];b[0][2]=0;d[0]=b[0][0];d[1]=b[0][1];k1=2;k2=0;k3=0,m1=1;while(k1<=n){for(i=1;i<m;i++)if(b[i][2]){for(j=0;j<k1;j++)if(b[i][0]==d[j])k2++;for(j=0;j<k1;j++)if(b[i][1]==d[j])k3++;if(k2&&!k3){d[k1++]=b[i][1];for(k=0;k<3;k++)c[m1][k]=b[i][k];b[i][2]=0;m1++;k2=0;goto h;}else if(!k2&&k3){d[k1++]=b[i][0];for(k=0;k<3;k++)c[m1][k]=b[i][k];b[i][2]=0;m1++;k3=0;goto h;}else{k2=k3=0;}}h:;}cout<<"用Prim算法得到的最小生成树为：\n{";count=0;for(i=0;i<n-2;i++){cout<<"("<<(char)(c1+c[i][0])<<","<<(char)(c1+c[i][1])<<"),";count+=c[i][2];}cout<<"("<<(char)(c1+c[n-1][0])<<","<<(char)(c1+c[n-1][1])<<")}\n"; count+=c[n-1][2];cout<<"最小权和为："<<count<<endl<<endl;system("pause");}。