了解Kruskal算法的优缺点：如何在Python中使用该算法构建最小生成树

# 定义边的结构体
class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

# 定义并查集的数据结构
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [1] * n

    # 查找根节点
    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    # 按秩合并
    def unite(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        self.rank[px] += self.rank[py]
        return True

# 定义Kruskal算法
def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x.w)  # 按边权从小到大排序
    res = []
    for e in edges:
        if uf.unite(e.u, e.v):
            res.append(e)
    return res

# 测试样例
edges = [
    Edge(0, 1, 4),
    Edge(0, 7, 8),
    Edge(1, 2, 8),
    Edge(1, 7, 11),
    Edge(2, 3, 7),
    Edge(2, 8, 2),
    Edge(2, 5, 4),
    Edge(3, 4, 9),
    Edge(3, 5, 14),
    Edge(4, 5, 10),
    Edge(5, 6, 2),
    Edge(6, 7, 1),
    Edge(6, 8, 6),
    Edge(7, 8, 7)
]
res = kruskal(9, edges)
for e in res:
    print("({}, {}) w={}".format(e.u, e.v, e.w))