kruskal算法

发表于 | 分类于

本章介绍kruskal算法

kruskal算法用途

wiki:
Kruskal算法是一种用来查找最小生成树的算法
用来解决同样问题的还有Prim算法和Boruvka算法等

算法步骤

1.依据已有的图G1 建立图G2 其中 图G2只有顶点，没有边
2.把原图G1中的边按权从小到大排序
3.从权最小的边开始 如果这条边相连的两个节点位于不同的连通分量中，那么就把这条边加入G2 反之 跳过这条边
4.重复 3 直到所有的节点在同一个连通分量中
算法结束
（我们说点v1和v2是连通的，如果这两个点有直接或者间接的边相连—–请参考[离散数学]）

算法正确性

我们先来说明一下这个算法的可行性
对于在T中的边e 如果它不在最小生成树T中 那么它相连的两个连通分量最终会被其他的边连起来 于是这些边可以与e构成环 那么在这个环里必存在一条比它大的边 那么我去掉这条边 可以保证图的连通性不变 这个时候图的总权值变小了。 也就是说 如果我不选去这条边 那么这颗树一定不是最小生成树。

算法实现

算法步骤挺容易懂的 怎么实现呢
我们可以把连通分量看成一个集合 加入边的过程 可以看成是把两个集合合并为一个集合的过程
这是不是和并查集有点像呢？

例题讲解

具体拿道题目来说HDOJ 1863
很明显这题是个最小生成树 村庄是图的顶点 道路是图的边
按照算法描述和并查集操作
先给出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>

using namespace std;

struct Edge{
    int from,to;
    int m;
    bool operator<(const Edge a)const{
        return this->m<a.m;
    }
};
int bin[105];
int rnk[105];
int n,m;
vector<Edge> edge;

inline void Init(){
    edge.clear();
    for(int i=0;i<=104;i++){
        bin[i]=i;
        rnk[i]=1;
    }
}

inline int find(int a){
    if(bin[a]!=a) a=bin[a];
    return a;
}

inline void merge(int a,int b){
    a=find(a);
    b=find(b);
    if(rnk[a]<=rnk[b]){
        bin[a]=b;
        if(rnk[a]==rnk[b]) rnk[b]++;
    }
    else rnk[b]=a;
    return;
}

inline int kruskal(){
    int tt=0;
    sort(edge.begin(),edge.end());
    int res=m;
    for(auto e:edge){
        if(find(e.from)!=find(e.to)){
            tt+=e.m;
            merge(e.from,e.to);
            res--;
        }
        if(res==1) break;
    }
    if(res==1) return tt;
    else return -1;
}

int main(){
    while(cin>>n>>m){
        if(n==0) break;
        Init();
        for(int i=1;i<=n;i++){
            int from,to,m;
            cin>>from>>to>>m;
            edge.push_back((Edge){from,to,m});
        }
        int ans=kruskal();
        if(ans==-1) cout<<"?"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

这里用了一点小小的技巧
请看kruskal算法主体部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline int kruskal(){
    int tt=0;
    sort(edge.begin(),edge.end());
    int res=m;
    for(auto e:edge){
        if(find(e.from)!=find(e.to)){
            tt+=e.m;
            merge(e.from,e.to);
            res--;
        }
        if(res==1) break;
    }
    if(res==1) return tt;
    else return -1;
}

这里用了res变量 用于记录图的连通分量的个数
如果整张图的连通分量==1 即图已经连通 那么我就可以不用再去选择边了 可以缩短时间