一、算法描述

在一个连通加权无向图中，找到一棵最小生成树。即，找到连接所有顶点的、权值总和最小的树，且树中不包含任何环。

二、核心思想

1. 贪心策略：每次从未选择的边中，选取一条权值最小的边。

2. 避免环路：如果加入这条边会导致生成树中形成环，则舍弃它。

3. 集合管理：使用并查集数据结构来高效地判断两个顶点是否已经连通（即加入边是否会形成环）。

三、图解过程

假设我们有以下连通图 G，目标是找到它的最小生成树（MST）。

步骤 0：初始化

• 将图中所有边按权值从小到大排序。

• 初始化一个空的边集 MST，用于存放最小生成树的边。

• 初始化并查集，让每个顶点自成一個集合。

排序后的边列表：(A,D):5, (C,E):5, (D,F):6, (A,B):7, (B,E):7, (B,C):8, (E,F):8, (B,D):9, ...

当前 MST： { }并查集状态： {A}, {B}, {C}, {D}, {E}, {F}

步骤 1：选择最小边 (A,D):5

• 检查：顶点 A 和 D 是否在同一集合？否（不会形成环）。

• 将边 (A,D) 加入 MST。

• 在并查集中合并集合 {A} 和 {D}。

  
  

当前 MST： { (A,D):5 }并查集状态： {A, D}, {B}, {C}, {E}, {F}

步骤 2：选择下一条最小边 (C,E):5

• 检查：顶点 C 和 E 是否在同一集合？否（不会形成环）。

• 将边 (C,E) 加入 MST。

• 合并集合 {C} 和 {E}。

当前 MST： { (A,D):5, (C,E):5 }并查集状态： {A, D}, {B}, {C, E}, {F}

步骤 3：选择边 (D,F):6

• 检查：顶点 D 和 F 是否在同一集合？否（D在{A,D}，F在{F}）。

• 将边 (D,F) 加入 MST。

• 合并集合 {A, D} 和 {F}。

当前 MST： { (A,D):5, (C,E):5, (D,F):6 }并查集状态： {A, D, F}, {B}, {C, E}

步骤 4：选择边 (A,B):7

• 检查：顶点 A 和 B 是否在同一集合？否（A在{A,D,F}，B在{B}）。

• 将边 (A,B) 加入 MST。

• 合并集合 {A, D, F} 和 {B}。

  
  

当前 MST： { (A,D):5, (C,E):5, (D,F):6, (A,B):7 }并查集状态： {A, B, D, F}, {C, E}

步骤 5：选择边 (B,E):7

• 关键检查：顶点 B 和 E 是否在同一集合？

• B 在 {A, B, D, F}

• E 在 {C, E}

• 不在同一集合（不会形成环）。

• 将边 (B,E) 加入 MST。

• 合并两个大集合 {A, B, D, F} 和 {C, E}。此时所有顶点都在同一个集合中。

当前 MST： { (A,D):5, (C,E):5, (D,F):6, (A,B):7, (B,E):7 }并查集状态： {A, B, C, D, E, F}

算法终止

• 终止条件：MST 中的边数 = 顶点数 - 1 = 5。我们已经找到了最小生成树。

• 后续的边 (B,C):8, (E,F):8, (B,D):9 等不再被考虑，因为加入它们都会连接已经连通的顶点，从而形成环。

最终的最小生成树（MST） 如上图红色边所示。总权值 = 5 + 5 + 6 + 7 + 7 = 30

关键要点总结

• 贪心选择：始终选择当前可用的、不构成环的最小权边。

• 环检测工具：并查集是高效实现 Kruskal 算法的关键，它能近乎 O(1) 时间完成“查找”和“合并”操作。

• 时间复杂度：

• 排序边：O(|E| log |E|)，其中 |E| 是边数。

• 并查集操作：近似 O(|E| α(|V|))，其中 α 是增长极慢的反阿克曼函数。

• 总复杂度主要取决于排序：O(|E| log |E|)。

• 适用场景：适用于稀疏图（边数 |E| 远小于顶点数 |V|² 的图），因为其复杂度主要由边数决定。

【参考代码】

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 边的结构体
struct Edge {
    int u;
    int v;
    int weight;
};
// 并查集结构体
struct UnionFind {
    vector<int> parent;  
    vector<int> rank;
};

// 初始化并查集
void initUnionFind(UnionFind& uf, int n) {
    uf.parent.resize(n);
    uf.rank.resize(n, 0);
    for (int i = 0; i < n; ++i) {
        uf.parent[i] = i;
    }
}

// 查找操作
int find(UnionFind& uf, int x) {
    if (uf.parent[x] != x) {
        uf.parent[x] = find(uf, uf.parent[x]);
    }
    return uf.parent[x];
}

// 合并操作
bool merge(UnionFind& uf, int x, int y) {
    int rootX = find(uf, x);
    int rootY = find(uf, y);
    if (rootX == rootY) return false;
    
    if (uf.rank[rootX] < uf.rank[rootY]) {
        uf.parent[rootX] = rootY;
    } else if (uf.rank[rootX] > uf.rank[rootY]) {
        uf.parent[rootY] = rootX;
    } else {
        uf.parent[rootY] = rootX;
        uf.rank[rootX]++;
    }
    return true;
}

// 比较函数
bool cmp(Edge a, Edge b) {
    return a.weight < b.weight;
}

// Kruskal算法
vector<Edge> kruskalMST(int n, vector<Edge>& edges) {
    // 1. 按边权升序排序
    sort(edges.begin(), edges.end(), cmp);
    // 2. 初始化并查集
    UnionFind uf;
    initUnionFind(uf, n);
    // 3. 构建最小生成树
    vector<Edge> mst;
    int mstWeight = 0;
    for (size_t i = 0; i < edges.size(); ++i) {
        const Edge& edge = edges[i];
        if (merge(uf, edge.u, edge.v)) {
            mst.push_back(edge);
            mstWeight += edge.weight;
            if (mst.size() == (size_t)(n - 1)) break;
        }
    }
    cout << "最小生成树总权重: " << mstWeight << endl;
    return mst;
}

int main() {
    int n = 6;
    vector<Edge> edges;
    // 添加边
    edges.push_back({0, 1, 4});
    edges.push_back({0, 2, 4});
    edges.push_back({1, 2, 2});
    edges.push_back({2, 3, 3});
    edges.push_back({2, 5, 2});
    edges.push_back({2, 4, 4});
    edges.push_back({3, 4, 3});
    edges.push_back({4, 5, 3});
    
    vector<Edge> mst = kruskalMST(n, edges);
    
    cout << "最小生成树包含的边:" << endl;
    for (size_t i = 0; i < mst.size(); ++i) {
        const Edge& edge = mst[i];
        cout << edge.u << " - " << edge.v << " : " << edge.weight << endl;
    }
    
    return 0;
}

输出

最小生成树总权重: 14
最小生成树包含的边:
1 - 2 : 2
2 - 5 : 2
2 - 3 : 3
3 - 4 : 3
0 - 1 : 4