最小生成树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算法是一种常用的图算法，用于找到一个连通图的最小生成树。下面是Kruskal算法的C++代码示例：

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

using namespace std;

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

// 定义并查集的数据结构
classFind {
public:
    vector<int> parent, rank;

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

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

    void unionSet(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]++;
            }
        }
    }
};

// Kruskal算法实现
vector<Edge> kruskalMST(vector<Edge>& edges, int V) {
    // 按照边的权重进行排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    vector<Edge> result;
    UnionFind uf(V);

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

        // 判断加入边后是否形成环路
        if (uf.find(src) != uf.find(dest)) {
            uf.unionSet(src, dest);
            result.push_back(edge);
        }
    }

    return result;
}

int main() {
    int V, E;
    cout << "请输入顶点数和边数：";
    cin >> V >> E;

    vector<Edge> edges(E);
    cout << "请输入每条边的起点、终点和权重：" << endl;
    for (int i = 0; i < E; i++) {
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }

    vector<Edge> mst = kruskalMST(edges, V);

    cout << "最小生成树的边：" << endl;
    for (const Edge& edge : mst) {
        cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;
    }

    return 0;
}