1. 算法概述

克鲁斯卡尔算法（Kruskal's Algorithm）是一种用于求解最小生成树（Minimum Spanning Tree, MST） 的经典贪心算法。它的核心特点是先将所有边按权重从小到大排序，然后依次考察每条边，如果该边连接的两个顶点当前不在同一个连通分量中（即加入后不会形成环），则将其加入生成树。该算法特别适用于稀疏图（边数较少的图）。

2. 核心思想

• 排序：将所有边按权重升序排列。
• 贪心选择：从小到大遍历每条边。
• 并查集判环：使用并查集（Union-Find）维护顶点的连通性。若一条边的两个端点不在同一集合中，则加入该边不会形成环，将其合并到同一个集合。
• 终止条件：当选出 V-1 条边时，最小生成树构建完成（V 为顶点数）。

3. 算法步骤/伪代码

Kruskal(G):
    sort all edges by weight ascending
    UF = UnionFind(V)
    mst_edges = []
    total_weight = 0

    for each edge (u, v, w) in sorted edges:
        if UF.find(u) != UF.find(v):
            UF.union(u, v)
            mst_edges.add(edge)
            total_weight += w
            if mst_edges.size() == V - 1:
                break

    return total_weight, mst_edges

4. C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// ==================== 并查集 ====================
class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) return;
        // 按秩合并
        if (rank[rx] < rank[ry]) {
            parent[rx] = ry;
        } else if (rank[rx] > rank[ry]) {
            parent[ry] = rx;
        } else {
            parent[ry] = rx;
            rank[rx]++;
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

// ==================== Kruskal 算法 ====================
struct Edge {
    int u, v, weight;
    Edge(int u, int v, int w) : u(u), v(v), weight(w) {}
};

int kruskal(int V, vector<Edge>& edges) {
    // 按权重升序排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    UnionFind uf(V);
    int totalWeight = 0;
    int edgeCount = 0;

    for (const Edge& e : edges) {
        if (!uf.connected(e.u, e.v)) {
            uf.unite(e.u, e.v);
            totalWeight += e.weight;
            edgeCount++;
            if (edgeCount == V - 1) break;
        }
    }

    // 若边数不足 V-1，说明图不连通
    if (edgeCount < V - 1) return -1;
    return totalWeight;
}

// ==================== 测试 ====================
int main() {
    // 示例：求 LeetCode 1584 连接所有点的最小费用
    // 点集：[(0,0), (2,2), (3,10), (5,2), (7,0)]
    vector<pair<int, int>> points = {
        {0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}
    };
    int V = points.size();

    // 建图：完全图，边权为曼哈顿距离
    vector<Edge> edges;
    for (int i = 0; i < V; i++) {
        for (int j = i + 1; j < V; j++) {
            int w = abs(points[i].first - points[j].first) +
                    abs(points[i].second - points[j].second);
            edges.push_back(Edge(i, j, w));
        }
    }

    int result = kruskal(V, edges);
    cout << "最小生成树总权重: " << result << endl;
    // 期望输出: 20

    return 0;
}

运行示例

最小生成树总权重: 20

5. 复杂度分析

• 时间复杂度：O(E log E)，其中 E 为边数。
  • 排序：O(E log E)
  • 并查集操作：近似 O(E · α(V))，α 为反阿克曼函数，可视为常数。
• 空间复杂度：O(V + E)，存储边列表和并查集。

当图为稀疏图（E ≈ V）时，复杂度接近 O(V log V)，十分高效。

6. 应用场景

场景	说明
网络布线	连接所有节点且总成本最低
电路设计	最小化 PCB 布线总长度
聚类分析	单链聚类（Single-linkage Clustering）
图像分割	基于图的分割算法（Graph-based Segmentation）
交通/通信网络	修建公路、光缆的最小总费用

7. 经典例题

LeetCode 1584. 连接所有点的最小费用

题目描述：给你一个 points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi]。连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的曼哈顿距离：|xi - xj| + |yi - yj|。请返回将所有点连接的最小总费用。

解题思路：将每个点看作图的顶点，任意两点间的曼哈顿距离作为边权。问题转化为求完全图的最小生成树。由于是完全图，边数为 O(n²)，Kruskal 算法复杂度为 O(n² log n)，在 n ≤ 1000 时可通过。

关键代码要点：

1. 生成所有边（n 个点产生 n×(n-1)/2 条边）
2. 对所有边按曼哈顿距离排序
3. 使用并查集依次加入边，计数达到 n-1 时停止

扩展思考：当 n 较大时，可使用 Prim 算法（朴素 O(n²) 或堆优化）获得更优性能。