数据结构最小生成树的克鲁斯卡尔算法

克鲁斯卡尔算法是一种求带权无向图的最小生成树的构造性算法。其基本思想是按照边权值从小到大的顺序，依次选择n-1条边，并保证这n-1条边不构成回路，直到选出的边数达到n-1为止。

具体实现步骤如下：
1. 将图中所有边按照权值从小到大排序。
2. 从权值最小的边开始，依次判断该边的两个端点是否在同一个连通块中，如果不在，则将这条边加入最小生成树中，并将这两个端点所在的连通块合并。
3. 重复步骤2，直到选出的边数达到n-1为止。

下面是一个Python实现的例子：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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):
        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[py] = px
            self.rank[px] += 1
        return True

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

# 示例
n = 5
edges = [(0, 1, 2), (0, 3, 6), (1, 2, 3), (1, 3, 8), (1, 4, 5), (2, 4, 7), (3, 4, 9)]
res = kruskal(n, edges)
print(res) # 输出：[(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)]