python的kruskal算法

Kruskal算法是一种用于求解最小生成树的算法，它是基于贪心策略的。下面是一个用Python实现Kruskal算法的示例代码：

# 定义边的数据结构
class Edge:
    def __init__(self, src, dest, weight):
        self.src = src
        self.dest = dest
        self.weight = weight

# 定义并查集数据结构
class UnionFind:
    def __init__(self, vertices):
        self.parent = {}
        self.rank = {}

        for v in vertices:
            self.parent[v] = v
            self.rank[v] = 0

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

    def union(self, v1, v2):
        root1 = self.find(v1)
        root2 = self.find(v2)

        if self.rank[root1] < self.rank[root2]:
            self.parent[root1] = root2
        elif self.rank[root1] > self.rank[root2]:
            self.parent[root2] = root1
        else:
            self.parent[root2] = root1
            self.rank[root1] += 1

# Kruskal算法实现
def kruskal(vertices, edges):
    mst = []

    # 按照权重对边进行排序
    edges.sort(key=lambda x: x.weight)

    uf = UnionFind(vertices)

    for edge in edges:
        src_root = uf.find(edge.src)
        dest_root = uf.find(edge.dest)

        if src_root != dest_root:
            mst.append(edge)
            uf.union(src_root, dest_root)

    return mst

这段代码中，我们首先定义了边的数据结构`Edge`，包括边的起点、终点和权重。然后定义了并查集数据结构`UnionFind`，用于判断两个顶点是否在同一个集合中。最后实现了Kruskal算法`kruskal`，通过对边按权重排序，并使用并查集来判断是否形成环路，从而构建最小生成树。

你可以根据自己的需求调用`kruskal`函数，并传入顶点列表和边列表来求解最小生成树。