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

以下是Kruskal算法实现最小生成树的Python代码：

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])
    dsu = DisjointSet(n)
    mst = []
    for u, v, w in edges:
        if dsu.find(u) != dsu.find(v):
            mst.append((u, v))
            dsu.union(u, v)
        if len(mst) == n-1:
            break
    return mst

n, m = map(int, input().split())
vertices = [input() for _ in range(n)]
edges = []
for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))
mst = kruskal(n, edges)
for u, v in mst:
    if u < v:
        print(f'({u},{v})', end=' ')
    else:
        print(f'({v},{u})', end=' ')

注意，这里使用了一个 `DisjointSet` 类来维护连通性，`kruskal()` 函数则是按照边权从小到大排序，每次选择权值最小且不会形成环的边加入最小生成树中，直到加入了 $n-1$ 条边为止。最后输出最小生成树的边即可。