最小生成树kruskal算法 c++

很高兴能回答关于最小生成树kruskal算法的问题。这是一种常见的贪心算法，用于找到一个连通图的最小生成树。这个算法的关键在于对边的权重进行排序，然后从小到大依次加入图中，直到所有的节点都连通为止。同时，该算法使用并查集来判断是否形成环路，以避免出现重复边的情况。如果您还有其他问题，可以继续提问。谢谢！

相关问题

最小生成树kruskal算法c++

以下是使用C++实现Kruskal算法求最小生成树的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

// 定义并查集的数据结构
struct DisjointSet {
    int *parent, *rank;
    int n;

    DisjointSet(int n) {
        this->n = n;
        parent = new int[n];
        rank = new int[n];

        // 初始化每个节点的父节点为自身，秩为0
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // 查找节点的根节点
    int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    // 合并两个集合
    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
};

// Kruskal算法求最小生成树
void kruskal(vector<Edge>& edges, int n) {
    // 按照边的权重进行排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    vector<Edge> result; // 存储最小生成树的边
    DisjointSet ds(n);

    for (const auto& edge : edges) {
        int src = edge.src;
        int dest = edge.dest;

        // 判断两个节点是否在同一个集合中
        if (ds.find(src) != ds.find(dest)) {
            result.push_back(edge);
            ds.merge(src, dest);
        }
    }

    // 输出最小生成树的顶点集合和边的集合
    cout << "顶点集合：";
    for (int i = 0; i < n; i++) {
        cout << i << " ";
    }
    cout << endl;

    cout << "边的集合：";
    for (const auto& edge : result) {
        cout << "(" << edge.src << ", " << edge.dest << ") ";
    }
    cout << endl;
}

int main() {
    int n = 6; // 图的顶点数

    // 定义图的边集合
    vector<Edge> edges = {
        {0, 1, 4},
        {0, 2, 3},
        {1, 2, 1},
        {1, 3, 2},
        {2, 3, 4},
        {3, 4, 2},
        {4, 5, 6}
    };

    kruskal(edges, n);

    return 0;
}

贪心算法最小生成树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;
}