用c++写出克鲁斯卡尔算法的方法

克鲁斯卡尔(Kruskal's)算法是一种用于寻找连通无向加权图中最小生成树的贪心算法。下面是使用C++实现的基本步骤：

#include <iostream>
#include <vector>
#include <set>
using namespace std;

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

bool compareEdges(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight; // 按照权重升序排列
}

void kruskalMST(vector<Edge>& edges, vector<int>& parent, int n) {
    sort(edges.begin(), edges.end(), compareEdges); // 排序边按权重

    set<int> mstSet; // 存储最小生成树的边
    int result = 0; // 最小生成树的总权重

    for(int i=0; i<edges.size(); i++) {
        Edge e = edges[i];

        if(mstSet.find(e.src) == mstSet.end() && mstSet.find(e.dest) == mstSet.end()) { // 如果边的两个端点均不在 MST 中
            parent[e.src] = e.dest; // 添加边到 MST
            parent[e.dest] = e.src;
            mstSet.insert(e.src);
            mstSet.insert(e.dest);
            result += e.weight; // 更新最小生成树的总权重
        }
    }

    cout << "Minimum Spanning Tree of given Graph is:\n";
    for(auto node : mstSet) {
        cout << "Edge (" << node << ", " << parent[node] << ") with weight " << edges[mstSet.find(node)-edges.begin()].weight << endl;
    }
    cout << "Total weight of MST: " << result << "\n";
}

int main() {
    int n, numEdges;
    cout << "Enter number of vertices: ";
    cin >> n;
    cout << "Enter number of edges: ";
    cin >> numEdges;

    vector<Edge> edges(numEdges);
    cout << "Enter edge weights and endpoints:\n";
    for(int i=0; i<numEdges; i++) {
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }

    vector<int> parent(n, -1); // 初始化每个节点的父亲为 -1 表示没有父节点
    kruskalMST(edges, parent, n);

    return 0;
}

这个程序首先输入图的顶点数和边的数量，然后读取每条边的源、目的地和权重。接着，它按照权重对边进行排序，执行克鲁斯卡尔算法，最后输出最小生成树及其总重量。