克鲁斯卡尔最小生成树算法C++代码

下面是克鲁斯卡尔最小生成树算法的C++代码示例：

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

using namespace std;

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

// 并查集的结构体
struct Subset {
    int parent, rank;
};

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

// 查找操作，寻找元素所属集合的根节点
int find(vector<Subset>& subsets, int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

// 合并操作，将两个集合进行合并
void unionSet(vector<Subset>& subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    
    if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;
    }
    else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;
    }
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

// 克鲁斯卡尔最小生成树算法
void kruskalMST(vector<Edge>& edges, int V) {
    vector<Edge> result;  // 存储最小生成树的边
    
    // 按照边的权重进行排序
    sort(edges.begin(), edges.end(), compare);
    
    vector<Subset> subsets(V);
    for (int i = 0; i < V; i++) {
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }
    
    int e = 0;  // 用于控制结果数组的下标
    int i = 0;  // 用于控制排序后的边数组的下标
    
    while (e < V - 1 && i < edges.size()) {
        Edge nextEdge = edges[i++];
        
        int x = find(subsets, nextEdge.src);
        int y = find(subsets, nextEdge.dest);
        
        if (x != y) {
            result.push_back(nextEdge);
            unionSet(subsets, x, y);
            e++;
        }
    }
    
    // 输出最小生成树的边及其权重
    cout << "最小生成树的边：" << endl;
    for (int i = 0; i < result.size(); i++) {
        cout << result[i].src << " - " << result[i].dest << "，权重：" << result[i].weight << endl;
    }
}

int main() {
    int V, E;
    cout << "请输入顶点数：";
    cin >> V;
    cout << "请输入边数：";
    cin >> E;
    
    vector<Edge> edges(E);
    
    for (int i = 0; i < E; i++) {
        cout << "请输入第 " << i + 1 << " 条边的起点、终点和权重：";
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }
    
    kruskalMST(edges, V);
    
    return 0;
}

这段代码实现了克鲁斯卡尔最小生成树算法，通过输入顶点数和边数，然后逐条输入边的起点、终点和权重，最后输出最小生成树的边及其权重。注意，该代码中使用了并查集来判断是否形成环路，并使用了排序算法进行边的排序。