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

实验5 最小生成树算法的设计与实现
一、 实验目的
1、 根据算法设计需要，掌握连通图的灵活表示方法；
2、 掌握最小生成树算法，如Prim、Kruskal算法；
3、 基本掌握贪心算法的一般设计方法；
4、 进一步掌握集合的表示序
详细代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN_E 100000
#define MAXN_V 100000
using namespace std;
struct Edge{
int fm,to,dist; 〃边的起始顶点，边的到达顶点，边权
}e[MAXN_E];
int fa[MAXN_V],n,m; 〃顶点数组，顶点总数，边总数
〃定义比较，只是边权比较
bool cmp(Edge a,Edge b){
return < ;
}
〃查找x的祖先
int getfa(int x){//getfa是在并查集森林中找到x的祖先
if(fa[x]==x) return fa[x];
else return fa[x] = getfa(fa[x]);
}
〃判断祖先是否是同一个，即是否联通
int same(int x,int y){
return getfa(x)==getfa(y);
}
〃合并两棵树
void merge(int x,int y){
int fax=getfa(x),fay=getfa(y);
fa[fax]=fay;
}
int main(){
int i;
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<<"请输入边的信息(例子：1 4 5从顶点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); 〃对边按边权进行升序排序
int rst=n,ans=0;//rst表示目前的点共存在于多少个集合中，初始情况是每
个点都在不同的集合中
for(i=1;i<=m && rst>1;i++)
{
int x=e[i].fm,y=e[i].to;
if(same(x,y)) continue;//same函数是查询两个点是否在同一集合中
else
{
merge(x,y);//merge函数用来将两个点合并到同一集合中
rst--;//每次将两个不同集合中的点合并，都将使rst值减1
ans+=e[i].dist;//这条边是最小生成树中的边，将答案加上边权
}
}
cout<<ans;
return 0;
}
五、测试数据和相应的最小生成树
■ ' F 土算十与分析s kal