Kruskal算法详解（C++语言实现最小生成树的完整教程）

实现步骤概览

1. 将图中所有边按权重从小到大排序。
2. 初始化一个并查集，每个顶点自成一个集合。
3. 遍历排序后的边：
   • 若当前边的两个顶点不在同一集合中，则将该边加入MST，并合并这两个集合。
   • 否则跳过（避免成环）。
4. 当MST包含 n-1 条边时，算法结束。

C++代码实现

下面是一个完整的、可运行的C++实现，包含详细的注释：

// Kruskal算法 C++实现#include <iostream>#include <vector>#include <algorithm>using namespace std;// 定义边结构体struct Edge {    int u, v, weight;        // 用于排序的比较函数    bool operator<(const Edge& other) const {        return weight < other.weight;    }};// 并查集类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 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]++;            }        }    }    bool connected(int x, int y) {        return find(x) == find(y);    }};// Kruskal算法主函数int kruskal(int n, vector<Edge>& edges) {    sort(edges.begin(), edges.end()); // 按权重升序排序    UnionFind uf(n);    int mstWeight = 0;    int edgeCount = 0;    for (const Edge& e : edges) {        if (!uf.connected(e.u, e.v)) {            uf.unite(e.u, e.v);            mstWeight += e.weight;            edgeCount++;            cout << "选择边: (" << e.u << ", " << e.v << ") 权重: " << e.weight << endl;                        if (edgeCount == n - 1) break;        }    }    return mstWeight;}// 主函数示例int main() {    int n = 4; // 顶点数    vector<Edge> edges = {        {0, 1, 10},        {0, 2, 6},        {0, 3, 5},        {1, 3, 15},        {2, 3, 4}    };    cout << "Kruskal算法执行过程：\n";    int total = kruskal(n, edges);    cout << "\n最小生成树总权重: " << total << endl;    return 0;}

代码说明

• Edge结构体：存储一条边的起点、终点和权重，并重载了<运算符以便排序。
• UnionFind类：实现了路径压缩和按秩合并的优化，使查找和合并操作接近常数时间。
• kruskal函数：主逻辑，先排序边，再逐个检查是否加入MST。

复杂度分析

Kruskal算法的时间复杂度主要由排序决定，为 O(E log E)，其中 E 是边的数量。并查集操作接近 O(α(V))（α 是反阿克曼函数，增长极慢），因此整体效率很高。

总结

通过本教程，你已经掌握了如何用C++实现Kruskal算法来求解最小生成树。该算法结合并查集实现，是图论算法中的经典范例。建议你动手运行代码，修改输入数据，加深理解。掌握它，你就离精通算法又近了一步！