实验5---最小生成树算法的设计与实现(报告).doc

实验5最小生成树算法的设计与实现
实验目的
1、根据算法设计需要,掌握连通图的灵活表示方法；
2、掌握最小生成树算法，如Prim、Kruskal算法；
3、基本掌握贪心算法的一般设计方法；
4、进一步掌握集合的表示与操作算法的应用。
实验内容
1、认真阅读算法设计教材和数据结构教材内容,熟习连通图的不同表示方法和最小生成树算法；
2、设计Kruskal算法实验程序。
有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。
设计测试问题,修改并调试程序,输出最小生成树的各条边,直至正确为止。
Kruskal算法的原理方法
边权排序:
131
462
364
145
235
345
256
126
356
566
1.初始化时：属于最小生成树的顶点U={}
不属于最小生成树的顶点V={1，2，3，4，5，6}
2.根据边权排序，选出还没有连接并且权最小的边（131），属于最小生成树的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6}

3.根据边权排序，选出还没有连接并且权最小的边（462），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5}

4.根据边权排序，选出还没有连接并且权最小的边（364），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5}

5.根据边权排序，选出还没有连接并且权最小的边（364），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5}

6.根据边权排序，选出还没有连接并且权最小的边（364），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成

实验程序的功能模块
功能模块：
boolcmp(Edgea,Edgeb)；//定义比较方法
intgetfa(intx)；//在并查集森林中找到x的祖先
intsame(intx,inty)；//判断祖先是否是同一个，即是否联通
voidmerge(intx,inty);//合并子树，即联通两子树
sort(e+1,e+m+1,cmp);//对边按边权进行升序排序
详细代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#defineMAXN_E100000
#defineMAXN_V100000
usingnamespacestd;
structEdge{
intfm,to,dist;//边的起始顶点，边的到达顶点，边权
}e[MAXN_E];
intfa[MAXN_V],n,m;//顶点数组，顶点总数，边总数
//定义比较，只是边权比较
boolcmp(Edgea,Edgeb){
returna.dist<b.dist;
}
//查找x的祖先
intgetfa(intx){//getfa是在并查集森林中找到x的祖先
if(fa[x]==x)returnfa[x];
elsereturnfa[x]=getfa(fa[x]);
}
//判断祖先是否是同一个，即是否联通
intsame(intx,inty){
returngetfa(x)==getfa(y);
}
//合并两棵树
voidmerge(intx,inty){
intfax=getfa(x),fay=getfa(y);
fa[fax]=fay;
}
intmain(){
inti;
cout<<"请输入顶点数目和边数目："<<endl;
cin>>n>>m;//n为点数，m为边数
//输出顶点信息
cout<<"各个顶点值依次为："<<endl;
for(i=0;i<n;i++)
{
fa[i]=i;
if(i!=0)
cout<<fa[i]<<"";
}
cout<<endl;
cout<<"请输入边的信息（例子：145从顶点1到顶点4的边权为5）"<<endl;
for(i=1;i<=m;i++)
cin>>e[i].fm>>e[i].to>>e[i].dist;//用边集数组存放边，方便排序和调用
sort(e+1,e+m+1,cmp);//对边按边权进行升序排序
intrst=n,ans=0;//rst表示目前的点共存在于多少个集合中，初始情况是每个点都在不同的集合中
for(i=1;i<=m&&rst>1;i++)
{
intx=e[i].fm,y=e[i].to;
if(same(x,y))continue;//same函数是查询两个点是否在同一集合中
else
{
merge(x,y);//merge函数用来将两个点合并到同一集合中
rst-