python最小生成树的kruskal算法

Kruskal算法是一种用于查找最小生成树的贪心算法，它的基本思想是从所有边中选取权值最小的边，直到所有顶点都在同一个连通块中为止。Python语言中实现Kruskal算法可以遵循以下步骤：

1. 首先将所有边按照权值从小到大排序。
2. 初始化一个空的集合来存储最小生成树中的边。
3. 对于每一条边，检查它的两个端点是否在同一个连通块中。如果不在同一个连通块中，则将这条边加入到最小生成树的集合中，并将这两个端点合并到同一个连通块中。
4. 重复步骤3，直到所有顶点都在同一个连通块中为止。

下面是Kruskal算法的Python代码实现：

def kruskal(graph):
    # 将所有边按照权值从小到大排序
    edges = sorted(graph['edges'], key=lambda x: x)
    
    # 初始化一个空的集合来存储最小生成树中的边
    mst = set()
    
    # 初始化每个顶点所在的连通块
    parent = {}
    for vertex in graph['vertices']:
        parent[vertex] = vertex
    
    # 查找顶点所在的连通块
    def find(parent, vertex):
        if parent[vertex] != vertex:
            parent[vertex] = find(parent, parent[vertex])
        return parent[vertex]
    
    # 合并两个连通块
    def union(parent, rank, x, y):
        xroot = find(parent, x)
        yroot = find(parent, y)
        
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1
    
    # 对于每一条边，检查它的两个端点是否在同一个连通块中
    for edge in edges:
        u, v, weight = edge
        
        if find(parent, u) != find(parent, v):
            mst.add(edge)
            union(parent, rank, u, v)
    
    return mst