数据结构与算法学习笔记----Kruskal算法

数据结构与算法学习笔记----Kruskal算法

@@ author: 明月清了个风
@@ first publish time: 2024.12.21

ps⭐️这也是一个思想比较简单的算法，只写了基本思想，具体的可以看代码理解一下

Kruskal算法

Kruskal算法同样是一种基于贪心策略的最小生成树求解算法，另一种是上一篇中的Prim算法。

基本思想

1. 将所有的边按边长从小到大排序。
2. 遍历所有边，判断每条边所连接的两个节点是否已经在树中，若没有则将这条边加入生成树，并合并两个节点所在的点的集合。

当树中已经有了$n-1$条边时，算法结束，若最后没有$n-1$条边，则表示无法生成。

时间复杂度

Kruskal算法的时间复杂度最高的地方为第一步中对所有边的排序，时间复杂度为$O(m\log m)$，$m$为边数，因此这个算法更加适合稀疏图的最小生成树求解问题。

第二步中我们需要进行的操作是将两个点集合并的操作，这个操作可以通过并查集（不知道看这个链接）来实现，对于并查集来说这个是常数级别的操作。

Acwing 859. Kruskal算法求最小生成树

[原题链接](859. Kruskal算法求最小生成树 - AcWing题库)

给定一个$n$个点$m$条边的有向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

给定一张边带权的无向图$G=(V,E)$，其中$V$表示图中点的集合，$E$表示图中边的集合，$n=|V|$，$m=|E|$。

由$V$中的全部$n$个顶点和$E$中$n-1$条边构成的无向连通子图被称为$G$的一棵生成树，其中边的权值之和最小的生成树被称为无向图$G$的最小生成树。

输入格式

第一行包含三个整数$n$,$m$。

接下来$m$行，每行包含三个整数$x$、$y$、$z$，表示存在一条从点$x$到点$y$的有向边，边长为$z$。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible.

数据范围

$1\le n\le 10^5$,

$1\le m\le 2\ast 10^5$,

图中涉及边长绝对值均不超过$1000$.

代码

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

using namespace std;

const int N = 100010, M = N * 2, inf = 0x3f3f3f3f;

struct Edge // 我们需要将所有的边进行排序，因此存储可以选择结构体，重载一下运算符就行了，排序用库函数即可
{
    int a, b, w;
    
    bool operator< (const Edge &W)const   
    {
        return w < W.w;
    }
}edges[M];

int n, m;
int p[N];

int find(int x)   // 并查集的找父节点操作，不知道的画可以看一下上文并查集链接中的文章
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);
    
    for(int i = 1; i <= n; i ++) p[i] = i;  // 初始化并查集
    
    int res = 0, cnt = 0;
    for(int i = 0; i < m; i ++)   // 从小到大遍历所有的边
    {
        auto t = edges[i];
        int a = t.a, b = t.b, w = t.w;
    
        int pa = find(a), pb = find(b);  // 找到这条边两个节点所在的集合
        if(pa != pb)  // 若两个点不在同一个集合中，合并两个点集
        {
            p[pa] = pb;
            res += w;   // 将这条边长加入最小生成树的边权总和中
            cnt ++; // 记录最小生成树中的边数
        }
    }
    
    if(cnt < n - 1) return inf;  // 最小生成树边数小于n - 1，表示生成失败，有点无法连通。
    return res;
}

int main()
{
    cin >> n >> m;
    
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    
    int t = kruskal();
    
    if(t == inf) puts("impossible");
    else cout << t << endl;
    
    return 0;
}