图论之Kruskal

一、前言

对于最小生成树的问题来说的话，我们可以发现如果直接利用我们的dijkstra算法，每次去遍历一个点，然后通过一个点的话去更新其他的所有边，在这样的过程中，换一个理解的方式来看的话，不过就是把我们所有的最短的边连起来，也就是，我们尝试将所有有关系的点通过最短的概念，连接起来，然后能够通过这样的方式，在集合内部已经连好的点，就不会在继续连，也就是我们一旦选定两个点进行边的连接的话，我们一定会选最短的，然后最后我们判断一下是否所有的点到最后会被连接到一个集合之中就好了。有了这个思路，我们其实就可以利用今天所讲到的Kruskal算法进行最短边的尝试，知道我们能够去让所有点入集合。

本章题大多来源于ACwing,欢迎大家来这个平台一起学习算法！！

二、题目汇总

①Kruskal算法模板(ACwing.859)

相关分析

时间复杂度: $O(mlogn)$

适用场景: 点数和边数都比较多的最小生成树的问题，应用面广于之前所说的Prim算法。

思路: 将所有的边进行排序，贪心的从最短的边开始遍历，一旦发现我们遍历的那个边能够加到我们的集合中的话，我们就可以加到我们的集合当中去的话就加入。那么判断这个边是否能够加入我们之前的集合当中去，无非就是看一下这个边加入集合后，会不会破坏我们的生成树的条件，而我们知道，一棵树只有一个根节点，我们只要满足每次加入的时候保证根节点只有一个就好了，这里就可以用并查集进行优化，最后我们只要判断一下是否所有边的数量为n - 1就好了！

完整AC代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 5, M = 2 * N + 10;

//因为是遍历所有的边，用结构体装一下就好了
struct Edge {
    //代表a, b有一条权值为c的边
    int a, b, c;
    //为了按照边从小到大排序的话，需要重载一下小于号
    //这里的写法主要是学比如写的，具体其实两个const和一个&不要也可以的
    bool operator< (const Edge& W) const {
        return c < W.c;
    }
}edges[M];
//并查集的pre数组
int pre[N];

//并查集加路径压缩的函数写法
int find(int x) {
    if(x != pre[x]) pre[x] = find(pre[x]);
    return pre[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    //初始化一下我们的并查集的点
    for(int i = 1; i <= n; i ++ ) pre[i] = i;
    
    for(int i = 0; i < m; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    
    sort(edges, edges + m);
    //记录加的边,和最终的结果
    int cnt = 0, ans = 0;
    //遍历一下所有的边
    for(int i = 0; i < m; i ++ ) {
        auto t = edges[i];
        int f1 = find(t.a), f2 = find(t.b);
        
        if(f1 != f2) {
            //可以把边加入 
            cnt++;
            //把两个不相连的集合连起来
            pre[f1] = f2;
            ans += t.c;
            if(cnt == n - 1) break;
        }
    }
    
    if(cnt != n - 1) cout << "impossible" << endl;
    else cout << ans << endl;
    
    // cout << cnt << endl;
    
    return 0;
}

②未完待续