Kruskal算法实现最小生成树 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。 输入图的相关信息，使用Kruskal算法，生成最小生成树。 输入说明： 先输入图中顶点个数和边的数目，空格间隔； 然后输入每个顶点的数据； 最后依次输入每条边的起始和终止顶点的位序及边上的权值，格式为：顶点1位序 顶点2位序 权值。 输出说明： 按生成次序依次输出最小生成树中的各边的起始顶点位序和终止顶点位序，用英文逗号间隔，一对圆括号括起来，且较小的顶点在前。

很高兴为您解答这道题目，以下是该题的C++代码实现：

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

const int MAXN = 1005;

int n, m;
int fa[MAXN], rk[MAXN];

struct Edge {
    int u, v, w;
    bool operator<(const Edge& rhs) const {
        return w < rhs.w;
    }
} edges[MAXN * MAXN];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rk[x] < rk[y]) swap(x, y);
    fa[y] = x;
    rk[x] += rk[y];
}

void kruskal() {
    sort(edges, edges + m);
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        rk[i] = 1;
    }
    for (int i = 0; i < m; ++i) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v)) {
            unite(u, v);
            cout << "(" << min(u, v) << "," << max(u, v) << ")" << endl;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
    }
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    kruskal();
    return 0;
}

该算法的时间复杂度为 $O(m\log m)$，其中 $m$ 为边的数量。