Kruskal算法

Kruskal算法介绍

简介: Kruskal算法是由克鲁斯卡尔提出的，是用来求加权连通图的最小生成树的算法
时间复杂度: O(mlogm)
空间复杂度：O(m)
使用范围: 稀疏图(朴素版本的Prim算法的时间复杂度为O(n2), 堆优化版本的Prim算法时间复杂度为O(mlogn),稀疏图问题就用Kruskal算法,稠密图问题就用朴素版的Prim算法,堆优化版本的Prim算法没有Kruskal算法好并且比较难写）。无向图(有向图一般用不到)
核心思想: 贪心,按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路.
算法步骤:

1.按照边权重从小到大排序(有自环与重边没事)
2.从小到大遍历所有边,如果边上两点不在一个集合内，则选择这条边,并将两点合并成一个集合
3.通过判断边的条数来判断是否存在最小生成树

Kruskal算法核心代码

//这里只需要用结构体存边权关系即可,记得重载"<"运算符方便sort操作,当然还可以手写cmp替代这方法
struct Edge{
    int a, b, w;
    bool operator < (const Edge t) const {return w < t.w;}
}edges[maxn2];

//p[]表示集合,n表示点数,m表示边数
int p[maxn1], n, m;

//并查集初始化操作
void init(int n) {
    for(int i = 1; i <= n; ++i) p[i] = i;
}
//并查集查找操作
int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    sort(edges, edges + m);
    int cnt = 0, res = 0;  //一定记得初始化,cnt记录集合中边的数量
    for(int i = 0; i < m; ++i) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if(find(a) != find(b)) {
            p[find(a)] = find(b);
            cnt++;
            res += w;
        }
    }
//因为这里用到并查集所以边数最多为n-1这时候集合有n个点,若是循环还没有停止,也不会进入if里面的语句了,n个点在同一个集合内了
    if(cnt < n - 1) return INF;
    return res;
}

Kruskal算法题目

题目http://https://www.acwing.com/problem/content/861/
代码

#include <bits/stdc++.h>
using namespace std;
const int maxn1 = 1e5 + 10;
const int maxn2 = 2e5 + 10;
const int INF = 0x3f3f3f3f;
//这里只需要用结构体存边权关系即可,记得重载"<"运算符方便sort操作,当然还可以手写cmp替代这方法
struct Edge{
    int a, b, w;
    bool operator < (const Edge t) const {return w < t.w;}
}edges[maxn2];

//p[]表示集合,n表示点数,m表示边数
int p[maxn1], n, m;

//并查集初始化操作
void init(int n) {
    for(int i = 1; i <= n; ++i) p[i] = i;
}
//并查集查找操作
int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    sort(edges, edges + m);
    int cnt = 0, res = 0;  //一定记得初始化,cnt记录集合中边的数量
    for(int i = 0; i < m; ++i) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if(find(a) != find(b)) {
            p[find(a)] = find(b);
            cnt++;
            res += w;
        }
    }
//因为这里用到并查集所以边数最多为n-1这时候集合有n个点,若是循环还没有停止,也不会进入if里面的语句了,n个点在同一个集合内了
    if(cnt < n - 1) return INF;
    return res;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    init(n);
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a,b,w};
    }
    int res = kruskal();
    if(res == INF) puts("impossible");
    else cout << res << endl;
    return 0;
}