克鲁斯卡尔算法c++daima

以下是克鲁斯卡尔算法的C++代码实现：

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

using namespace std;

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

// 比较函数，用于对边按权重进行排序
bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

// 并查集的初始化
void init(vector<int>& parent, int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

// 查找祖宗节点
int find(vector<int>& parent, int x) {
    if (x != parent[x]) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

// 合并两个集合
void merge(vector<int>& parent, int a, int b) {
    int rootA = find(parent, a);
    int rootB = find(parent, b);
    if (rootA != rootB) {
        parent[rootA] = rootB;
    }
}

// 克鲁斯卡尔算法
void kruskal(vector<Edge>& edges, int n) {
    // 对边按权重进行排序
    sort(edges.begin(), edges.end(), compare);

    vector<int> parent(n);
    init(parent, n);

    vector<Edge> result;
    int cost = 0;

    for (Edge edge : edges) {
        int srcRoot = find(parent, edge.src);
        int destRoot = find(parent, edge.dest);

        // 如果两个顶点的祖宗节点不同，说明不会形成环，可以加入最小生成树
        if (srcRoot != destRoot) {
            result.push_back(edge);
            cost += edge.weight;
            merge(parent, srcRoot, destRoot);
        }
    }

    // 输出最小生成树的边和总权重
    for (Edge edge : result) {
        cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;
    }
    cout << "Total cost: " << cost << 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;
}