贪心算法最小生成树kruskal 算法c++

Kruskal's算法是一种用于寻找无向图最小生成树的贪心算法。以下是C++的基本实现步骤[^1]：

1. **初始化**：创建一个空的并查集结构（通常使用数组或哈希表），用来表示每个顶点所属的集合；建立一个优先队列（如`std::priority_queue`），以边的权重作为比较依据。

2. **边的排序**：遍历所有边，将它们按照权重从小到大插入优先队列。

3. **构建树**：从优先队列中取出权重最小的边 `(u, v)`。如果这条边连接的两个顶点 `u` 和 `v` 分属于不同的集合（通过并查集检查），则将这条边添加到最小生成树中，并合并这两个集合。重复此过程，直到树中有 `V - 1` 条边，其中 `V` 是图中的顶点数。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

// 并查集辅助结构
class DisjointSet {
public:
    std::unordered_map<int, int> parent;
    void make_set(int x) { parent[x] = x; }
    int find_set(int x) { return parent[x] == x ? x : parent[x] = find_set(parent[x]); }
    bool union_sets(int x, int y) {
        int px = find_set(x), py = find_set(y);
        if (px != py)
            parent[py] = px;
        return px != py;
    }
};

int kruskal(std::vector<std::pair<int, std{int, int>>> edges) {
    DisjointSet ds;
    std::priority_queue<std::pair<int, std::pair<int, int>>, std::vector<std::pair<int, std::pair<int, int>>>, std::greater<std::pair<int, std::pair<int, int>>>> pq;
    
    // 添加边到优先队列
    for (const auto& edge : edges) {
        pq.push(edge);
    }

    int result = 0;
    while (ds.parent.size() != ds.V) {
        int weight = pq.top().first;
        int u = pq.top().second.first;
        int v = pq.top().second.second;
        pq.pop();

        // 如果边不形成环
        if (!ds.union_sets(u, v)) {
            result += weight;
            ds.make_set(u); // 更新树的结构
        }
    }
    return result;
}

int main() {
    std::vector<std::pair<int, std::pair<int, int>>> edges = {{1, {0, 1}}, {2, {0, 2}}, {3, {1, 3}}, {4, {2, 4}}, {5, {3, 5}}}; // 示例边
    int mst = kruskal(edges);
    std::cout << "Minimum spanning tree cost: " << mst << "\n";
    return 0;
}