克鲁斯卡尔最小生成树代码c++

以下是一个使用克鲁斯卡尔算法实现最小生成树的C++代码示例：

#include <iostream>
#include <algorithm>
using namespace std;

struct Edge {
    int from;
    int to;
    int weight;
};

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

class KruskalMST {
private:
    Edge* edges;
    int numEdges;
    int numVertices;
    int* parent;

public:
    KruskalMST(Edge* edges, int numEdges, int numVertices) {
        this->edges = edges;
        this->numEdges = numEdges;
        this->numVertices = numVertices;
        parent = new int[numVertices];
        for (int i = 0; i < numVertices; i++) {
            parent[i] = i;
        }
    }

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

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        parent[rootX] = rootY;
    }

    void kruskal() {
        sort(edges, edges + numEdges, compare);
        Edge* result = new Edge[numVertices - 1];
        int count = 0;
        int i = 0;
        while (count < numVertices - 1) {
            Edge currentEdge = edges[i];
            int fromRoot = find(currentEdge.from);
            int toRoot = find(currentEdge.to);
            if (from != toRoot) {
                result[count] = currentEdge;
                unionSets(fromRoot,Root);
                count++;
            }
            i++;
        }
        cout << "最小生成树的边：" << endl;
        for (int i = 0; i < numVertices - 1; i++) {
            cout << result[i].from << " - " << result[i].to << " 权重：" << result[i].weight << endl;
        }
    }
};

int main() {
    int numVertices;
    int numEdges;
    cout << "输入顶点个数：" << endl;
    cin >> numVertices;
    cout << "输入边的个数：" << endl;
    cin >> numEdges;
    Edge* edges = new Edge[numEdges];
    for (int i = 0; i < numEdges; i++) {
        cout << "第" << i + 1 << "条路径：" << endl;
        cin >> edges[i].from;
        cin >> edges[i].to;
        cin >> edges[i].weight;
    }
    KruskalMST mst(edges, numEdges, numVertices);
    mst.kruskal();
    return 0;
}