用python写一个克鲁斯卡尔算法

下面是使用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):
        root_x = self.find(x)
        root_y = 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(graph):
    n = len(graph)
    edges = []

    # 构建边列表
    for i in range(n):
        for j in range(i + 1, n):
            if graph[i][j] != 0:
                edges.append((i, j, graph[i][j]))

    # 按边的权重进行排序
    edges.sort(key=lambda x: x[2])

    uf = UnionFind(n)
    mst = []

    # 遍历边列表，依次选取权重最小的边，加入最小生成树中
    for edge in edges:
        u, v, weight = edge
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append(edge)

    return mst


# 测试
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

minimum_spanning_tree = kruskal(graph)
for edge in minimum_spanning_tree:
    print(edge)

上述代码中，我们先定义了一个`UnionFind`类，用于维护并查集数据结构，实现了并查集的`find`和`union`操作。然后，我们定义了`kruskal`函数，用于执行克鲁斯卡尔算法。在该函数中，我们首先将图转化为边的列表，并按边的权重进行排序。然后，我们使用并查集来判断是否形成环路，并选择权重最小的边加入最小生成树中。

以上是一个基本的克鲁斯卡尔算法的实现。你可以根据实际需求进行修改和优化。