最小生成树.并查集.最短路.ppt

最小生成树并查集最短路
罗方炜
lfw2565295@
最小生成树
问题描述:某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
最小生成树
输入:测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。当N为0时,输入结束,该用例不被处理。输出:对每个测试用例,在1行里输出最小的公路总长度。
最小生成树
样例输入:
3
1 2 1 1 3 2 2 3 4
4
1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5
0
样例输出:
3
5
最小生成树
最小生成树:在一个具有几个顶点的连通图G中,如果存在子图G‘包含G中所有顶点和一部分边,且不形成回路,则称G’为图G的生成树,代价最小生成树则称为最小生成树。简称MST。
最小生成树
一般有两种算法:Prim和Kruskal算法

今天主要讲Kruskal算法,适用本题,给出的边数,复杂度elong(e) (其中e表示变数)
最小生成树
算法粗略描述:假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。
最小生成树
做法:
定义结点:
#define M 10005
struct node{
int x,y,w; //表示x到y需要花费w
}e[M];
int n,m,father[M]; //n定点数量,m边数量,father[M],每个定点所属集合
最小生成树
int kruskal(){
int res=0,k=1,j=0;
for(int i=1; i<=m; i++) father[i]=i; //初始化集合数组
while(k<n && j<m){ //需要n-1条边
int m1=e[j].x, m2=e[j].y;
int sn1=findroot(m1), sn2=findroot(m2);
I f(sn1!=sn2){
res+=e[j].w; k++; //生成数+1
unionset(sn1,sn2);
}j++;
}
if(k!=n) res=-1; //不可能的情况,产生不了最小生成树
return res;
}
最小生成树
int main(){
while(scanf("%d",&n) && n){
m=n*(n-1)/2;
for(int i=0; i<m; i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
sort(e,e+m,cmp);
//排序按边权w值从小到大排序
printf("%d\n",kruskal());
}
}