MST Kruskal 克鲁斯卡尔

ybjnb / 2024-10-19 / 原文

Kruskal算法实现最小生成树

复杂度 O(mlogm)

Kruskal算法是一种贪心算法，用于在加权无向图中找到最小生成树。以下是使用C++实现Kruskal算法的代码，包括详细的注释说明。

#include <bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;      // 使用标准命名空间

typedef long long ll;      // 定义长整型别名
const int N = 1e4 + 10;   // 定义节点的最大数量

int fa[N];                // 并查集数组，存储每个节点的父节点
const int inf = 1e9;      // 定义无穷大常量，用于初始化边的权重

// 并查集的查找函数，用于找到元素x的根节点
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

// 边的结构体，包含两个节点和边的权重
struct Edge {
    int a, b, c;
};

// 比较函数，用于排序边，按照权重从小到大
bool cmp(Edge e1, Edge e2) {
    return e1.c < e2.c;
}

int main() {
    ios::sync_with_stdio(0);  // 关闭cin和cout的同步
    cin.tie(0);               // 解除cin和cout的绑定
    cout.tie(0);              // 解除cout和cout的绑定

    int n, m;                 // 分别存储节点数和边数
    cin >> n >> m;            // 读取节点数和边数

    // 读取每条边的信息，并存储到edge数组中
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].a >> edge[i].b >> edge[i].c;
    }

    // 对边进行排序，使用cmp比较函数
    sort(edge + 1, edge + 1 + m, cmp);

    // 初始化并查集，每个节点的父节点都是自己
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }

    // 初始化最小生成树的总权重和已加入的边数
    int ans = 0;
    int cnt = 0;

    // 遍历每条边，使用并查集判断是否形成环
    for (int i = 1; i <= m; i++) {
        int a = edge[i].a, b = edge[i].b, c = edge[i].c;
        int ta = find(a);  // 找到节点a的根节点
        int tb = find(b);  // 找到节点b的根节点

        // 如果节点a和b不属于同一个集合，则将它们合并，并更新最小生成树的总权重
        if (ta != tb) {
            cnt++;
            ans += c;
            fa[ta] = tb;  // 将节点a的根节点设置为节点b的根节点
        }

        // 如果已经找到了n-1条边，则说明已经形成了最小生成树
        if (cnt == n - 1) {
            break;
        }
    }

    // 如果未找到n-1条边，则说明图不连通
    if (cnt != n - 1) {
        cout << "orz" << endl;  // 输出"orz"
    } else {
        cout << ans << endl;    // 输出最小生成树的总权重
    }

    return 0;
}