Kruskal算法的C++实现文档

Kruskal算法是一种经典的图论算法，用于生成最小生成树。以下是一个完整的C++实现代码示例，供大家参考学习。

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

// 定义边结构体
struct Edge {
    int src, dest, weight;
};

// 定义并查集
class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] == x)
            return x;
        return find(parent[x]);
    }

    void Union(int x, int y) {
        int xset = find(x);
        int yset = find(y);
        parent[xset] = yset;
    }
};

// Kruskal算法实现
vector<edge> kruskal(vector<edge>& edges, int v) {
    // 根据权重对边进行排序
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    vector<edge> result;
    UnionFind uf(v);

    int i = 0;
    while (result.size() < v - 1) {
        Edge next_edge = edges[i++];
        int x = uf.find(next_edge.src);
        int y = uf.find(next_edge.dest);

        // 如果加入该边不会构成环路，则加入最小生成树
        if (x != y) {
            result.push_back(next_edge);
            uf.Union(x, y);
        }
    }

    return result;
}

int main() {
    // 定义图的顶点数和边
    int v = 5;
    vector<edge> edges = {
        {0, 1, 2},
        {0, 4, 6},
        {1, 2, 3},
        {1, 4, 5},
        {2, 3, 1},
        {3, 4, 4}
    };

    // 调用Kruskal算法求解最小生成树
    vector<edge> min_spanning_tree = kruskal(edges, v);

    // 输出最小生成树的边和权重
    for (Edge edge : min_spanning_tree) {
        cout << edge.src << " - " << edge.dest << ": " << edge.weight << endl;
    }

    return 0;
}
edge>edge>edge>edge>edge>int>vector>algorithm>iostream>