图论算法：Kruskal 算法

什么是最小生成树 (MST)？

在一个 无向连通图 中，一个 生成树 是图的一个子图，它包含了图中所有的顶点，并且是一棵树（即，没有环）。一个图可以有多个生成树。

最小生成树 (Minimum Spanning Tree, MST) 是指在一个带权的无向连通图中，所有生成树里，边的权重之和最小的那一棵。

Kruskal 算法的核心思想

Kruskal 算法是一种基于 贪心策略 的最小生成树算法。它的思想非常直观和简单：

1. 将图中所有的边，按照权重从小到大进行排序。
2. 初始化一个空的边集合，用于存放最小生成树的边。
3. 从权重最小的边开始，依次遍历所有排好序的边。
4. 对于当前正在考虑的边 (u, v)，判断如果将这条边加入到我们已选择的集合中，是否会形成一个环。
   • 如果 不会 形成环，就选择这条边，将其加入集合。
   • 如果 会 形成环，就舍弃这条边。
5. 重复步骤 4，直到我们选择了 N-1 条边（N 是顶点数）。此时，这些边就构成了一棵最小生成树。

如何判断是否形成环？

判断环是 Kruskal 算法的关键。最高效的方法是使用 并查集 (Disjoint Set Union, DSU) 数据结构。

• 我们将图中的每个顶点初始化为一个独立的集合。
• 当我们考虑一条边 (u, v) 时，我们使用并查集的 find 操作来检查 u 和 v 是否已经在同一个集合中。
  • 如果 find(u) == find(v)，说明 u 和 v 已经连通了。此时再加入边 (u, v) 必然会形成环，所以我们舍弃这条边。
  • 如果 find(u) != find(v)，说明它们分属不同的连通块。加入这条边不会形成环，于是我们选择这条边，并使用并查集的 union 操作将 u 和 v 所在的集合合并。

C++ 伪代码

#include <vector>
#include <algorithm>

struct Edge {
    int u, v, weight;
};

struct DSU {
    std::vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        for (int i = 1; i <= n; ++i) parent[i] = i;
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
};

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

int kruskal(int n, std::vector<Edge>& edges) {
    std::sort(edges.begin(), edges.end(), compareEdges);
    DSU dsu(n);
    int total_weight = 0;
    int edges_count = 0;

    for (const auto& edge : edges) {
        if (dsu.find(edge.u) != dsu.find(edge.v)) {
            dsu.unite(edge.u, edge.v);
            total_weight += edge.weight;
            edges_count++;
            if (edges_count == n - 1) break;
        }
    }
    return total_weight;
}

复杂度分析

• 时间复杂度: O(E log E)，主要瓶颈在于对所有边进行排序。如果边的数量 E 远大于 V，也可以说是 O(E log V)。
• 适用性: Kruskal 算法适用于稀疏图，而另一种最小生成树算法 Prim 更适用于稠密图。