概念导入：什么是 Kruskal 算法？

📊 Kruskal 算法定义

Kruskal 算法是一种经典的 贪心算法，用于在加权无向图中寻找 最小生成树（Minimum Spanning Tree, MST）。

简单来说，目标是用最少的“成本”（边的权重之和）连接图中的所有顶点，并且不能形成任何环路。

  • 输入：一个连通的、无向的、带权的图。
  • 输出：一个包含图中所有顶点的树，且所有边的权重之和最小。
  • 核心思想：按边的权重从小到大依次选择，只要不形成环路就加入 MST。

💡 应用场景

最小生成树算法在现实世界中有很多用途：

  • 网络设计： 规划城市间成本最低的光纤网络、电网或公路网。
  • 电路布线： 在电路板上连接各个元件，使得使用的导线总长度最短。
  • 聚类分析： 在机器学习中，可用于基于距离的聚类算法。
  • 管道铺设： 设计供水或天然气管道网络，使总长度或成本最小。
  • 旅行商问题近似： MST 可以作为解决 TSP 问题的一种启发式方法。

任何需要以最低成本连接多个点的问题，都可能用到 MST 算法。

⚙️ 算法思路 (Kruskal)

Kruskal 算法的步骤非常直观：

  1. 排序： 将图中所有的边按照权重从小到大进行排序。
  2. 初始化： 将每个顶点视为一个独立的集合（一棵只有根节点的树）。通常使用 并查集 (Disjoint Set Union, DSU) 数据结构来维护这些集合。
  3. 迭代选边： 遍历排序后的边列表：
    • 对于当前边 `(u, v)`，检查顶点 `u` 和 `v` 是否属于同一个集合（即 `find(u) == find(v)`）。
    • 如果不属于同一个集合：将这条边加入 MST，并合并 `u` 和 `v` 所在的集合（`union(u, v)`）。
    • 如果属于同一个集合：忽略这条边，因为它会形成环路。
  4. 终止条件： 当 MST 中的边数达到 `顶点数 - 1` 时，算法结束，MST 构建完成。

🔬 算法演示：Kruskal 动态过程

图参数设置

算法控制

请点击“生成图”开始。

候选边 (按权重排序)

MST 边集 (0/0) | 总权重: 0

并查集状态 (DSU)

节点ParentRank/Size

⚔️ 算法对比：Kruskal vs Prim

Kruskal 算法 (基于边)

核心思想： 从全局视角出发，不断选择当前权重最小且不构成环的边加入生成树。

  • 总是选择全局最优的边。
  • 使用并查集 (DSU) 检测环路。
  • 适合稀疏图 (边数 E 接近顶点数 V)。
  • 时间复杂度：O(E log E) 或 O(E log V)，主要取决于排序和 DSU 操作。

Prim 算法 (基于顶点)

核心思想： 从一个起始顶点出发，逐步扩展生成树，每次选择连接已选顶点集与未选顶点集的最短边。

  • 像“生长”一棵树一样逐步扩展。
  • 使用优先队列 (最小堆) 维护待考察的边。
  • 适合稠密图 (边数 E 接近 V²)。
  • 时间复杂度：O(E log V) 使用二叉堆，或 O(E + V log V) 使用斐波那契堆。
特性 Kruskal 算法 Prim 算法
策略 贪心 (基于边) 贪心 (基于顶点)
数据结构 并查集 (DSU), 边排序 优先队列 (最小堆)
环路检测 通过 DSU 的 find 操作 通过检查边的另一端是否已在 MST 集合中
图结构 适用于稀疏图 适用于稠密图
实现复杂度 相对简单 (若 DSU 熟悉) 稍复杂 (若用堆优化)
时间复杂度 (常用) O(E log E) 或 O(E log V) O(E log V)
中间状态 森林 (多个连通分量) 始终是一棵树

📜 原理与代码实现

Kruskal 算法 C++ 实现 (核心逻辑)

#include <bits/stdc++.h>

// 定义边的结构体
struct Edge {
    int u, v, weight;
    // 为了排序
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

// 并查集 (Disjoint Set Union - DSU) 结构
struct DSU {
    vector<int> parent;
    vector<int> rank; // 或 size

    // 初始化 n 个节点，每个节点自成一个集合
    DSU(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0); // parent[i] = i
        rank.assign(n, 0); // 初始 rank 都为 0
    }

    // 查找节点 x 的根节点 (带路径压缩)
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并包含节点 x 和节点 y 的两个集合 (按秩合并)
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++; // 秩相同时，合并后秩加 1
            }
        }
    }
};

// Kruskal 算法主函数
// V: 顶点数, edges: 包含所有边的 vector
pair, int> kruskalMST(int V, vector& edges) {
    // 1. 按权重对所有边进行排序
    sort(edges.begin(), edges.end());

    // 2. 初始化并查集
    DSU dsu(V);

    vector mstEdges; // 存储最小生成树的边
    int mstWeight = 0;      // MST 的总权重
    int edgeCount = 0;        // 当前已加入 MST 的边数

    // 3. 遍历排序后的边
    for (const auto& edge : edges) {
        // 如果 MST 的边数已达到 V-1，则结束
        if (edgeCount == V - 1) {
            break;
        }

        // 检查加入这条边是否会形成环路
        if (dsu.find(edge.u) != dsu.find(edge.v)) {
            // 不形成环路：加入 MST 并合并集合
            mstEdges.push_back(edge);
            mstWeight += edge.weight;
            dsu.unite(edge.u, edge.v);
            edgeCount++;
        } // else: 形成环路，忽略这条边
    }

     // 如果图不连通，可能无法选满 V-1 条边
     if (edgeCount != V - 1) {
          // 可以选择返回错误或部分 MST
          cerr << "Warning: Graph might be disconnected. MST not fully formed." << endl;
     }

    return {mstEdges, mstWeight};
}
Prim 算法 C++ 实现 (核心逻辑 - 使用优先队列)

#include <bits/stdc++.h>
using namespace std;

const int INF = numeric_limits<int>::max();

// 定义邻接表表示图: vector of pairs (neighbor, weight)
// 定义优先队列中存储的元素: pair (weight, vertex)
// 注意：优先队列默认是大顶堆，需要存负权重或自定义比较器实现小顶堆

// Prim 算法主函数
// V: 顶点数, adj: 图的邻接表
pair<vector<pair<int, int>>, int> primMST(int V, const Graph& adj) {
    if (V == 0) return {{}, 0};

    // 优先队列存储 {-weight, vertex}，实现小顶堆效果
    priority_queue<MinHeapPair> pq;

    vector<int> key(V, INF);       // key[i] 存储连接到 MST 的最小边的权重
    vector<int> parent(V, -1);   // parent[i] 存储 MST 中 i 的父节点
    vector<bool> inMST(V, false); // 标记顶点是否已加入 MST

    // 1. 从顶点 0 开始
    key[0] = 0;
    pq.push({0, 0}); // {-weight, vertex}

    int mstWeight = 0;
    vector<pair<int, int>> mstEdges; // 存储 MST 的边 {u, v}

    // 2. 循环直到优先队列为空或找到 V-1 条边
    while (!pq.empty()) {
        // 提取当前连接到 MST 的最小权重的边所对应的顶点
        int u_weight = -pq.top().first; // 恢复正权重
        int u = pq.top().second;
        pq.pop();

        // 如果顶点 u 已经被加入 MST，则跳过
        if (inMST[u]) {
            continue;
        }

        // 将顶点 u 加入 MST
        inMST[u] = true;
        mstWeight += u_weight;
        if (parent[u] != -1) { // 添加边到结果集 (除了起始点)
            mstEdges.push_back({parent[u], u});
        }

        // 3. 遍历 u 的所有邻居 v
        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            // 如果 v 不在 MST 中，并且新的边权重更小
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                parent[v] = u;
                pq.push({-weight, v}); // 加入优先队列 (负权重)
            }
        }
    }

    return {mstEdges, mstWeight};
}