用c++编写程序实现Kruscal算法对于给定的连通网输出最小生成树中的各边

以下是使用C++编写的Kruskal算法的实现：

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

using namespace std;

class Edge {
public:
    int src, dest, weight;
};

class Graph {
public:
    int V, E;
    vector<Edge> edges;

    Graph(int v, int e) {
        V = v;
        E = e;
        edges.resize(e);
    }

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

    int find(vector<int> parent, int i) {
        if (parent[i] == -1)
            return i;
        return find(parent, parent[i]);
    }

    void Union(vector<int>& parent, int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset] = yset;
    }

    void kruskalMST() {
        vector<Edge> result(V);
        int e = 0;
        int i = 0;

        sort(edges.begin(), edges.end(), [this](Edge a, Edge b) { return compare(a, b); });

        vector<int> parent(V, -1);

        while (e < V - 1 && i < E) {
            Edge next_edge = edges[i++];

            int x = find(parent, next_edge.src);
            int y = find(parent, next_edge.dest);

            if (x != y) {
                result[e++] = next_edge;
                Union(parent, x, y);
            }
        }

        cout << "Edges in the minimum spanning tree:" << endl;
        for (i = 0; i < e; i++) {
            cout << result[i].src << " - " << result[i].dest << " : " << result[i].weight << endl;
        }
    }
};

int main() {
    int V, E;
    cout << "Enter the number of vertices in the graph: ";
    cin >> V;
    cout << "Enter the number of edges in the graph: ";
    cin >> E;

    Graph graph(V, E);

    for (int i = 0; i < E; i++) {
        cout << "Enter source, destination and weight of edge " << i + 1 << ": ";
        cin >> graph.edges[i].src >> graph.edges[i].dest >> graph.edges[i].weight;
    }

    graph.kruskalMST();

    return 0;
}

这个程序首先要求用户输入连通网的顶点数和边数。然后，用户需要依次输入每条边的起点、终点和权重。程序使用Kruskal算法找到最小生成树中的边，并将它们输出到控制台