求最小生成树的Kruskal算法

Kruskal算法是求解无向连通图的最小生成树的一种贪心算法，其基本思路是从小到大选择边，将边加入到已选边集合中，直到构成最小生成树为止。具体实现过程如下：

1. 将图中所有边按照权值从小到大排序。

2. 初始化一个空的集合，用于存储已选中的边。

3. 遍历排好序的边集合，对于每条边，判断其两个端点是否在同一个连通块中，如果不在，则将这条边加入到已选边集合中，并将这两个端点所在的连通块合并为一个连通块。如果在同一个连通块中，则跳过这条边。

4. 重复步骤3，直到已选边集合中的边数等于节点数减一，此时已经构成了最小生成树。

下面是Kruskal算法的Python实现代码：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[px] = py
            self.rank[py] += 1
        return True

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

其中，UnionFind类是并查集，用于判断节点是否在同一个连通块中；kruskal函数接受节点数和边集合作为参数，返回构成的最小生成树。