实现采用克鲁斯卡尔算法求最小生成树 设计一个程序

好的，这是一个简单的 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 = 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):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

# 克鲁斯卡尔算法求解最小生成树
def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda e: e.w)
    res = []
    for e in edges:
        if uf.find(e.u) != uf.find(e.v):
            uf.union(e.u, e.v)
            res.append(e)
    return res

# 测试用例
n = 5
edges = [
    Edge(0, 1, 2),
    Edge(0, 3, 6),
    Edge(1, 3, 8),
    Edge(1, 2, 3),
    Edge(1, 4, 5),
    Edge(2, 4, 7),
    Edge(3, 4, 9)
]

res = kruskal(n, edges)
for e in res:
    print(e.u, e.v, e.w)

这个程序可以处理具有 n 个顶点和 edges 列表中给定的 m 条边的无向图，其中每条边都由其两个端点和权重表示。程序使用并查集数据结构来维护连通性。它首先将边按权重从小到大排序，然后从最小的边开始遍历，如果两个端点不在同一个集合中，则将它们合并并添加到结果列表中。最后，程序返回包含最小生成树的边的列表。

希望这个示例对你有所帮助！