python最小生成树

Kruskal算法是一种用于求最小生成树的算法，可以使用Python实现。下面是一个简单的Python实现：

def find(parent, i):
    if parent[i] == i:
        return i
    return find(parent, parent[i])
 
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
 
def KruskalMST(graph):
 
    result =[] 
 
    i = 0
    e = 0 
 
    graph =  sorted(graph,key=lambda item: item[2])
 
    parent = [] ; rank = []
 
    for node in range(V):
        parent.append(node)
        rank.append(0)
    
    while e < V -1 :
 
        u,v,w =  graph[i]
        i = i + 1
        x = find(parent, u)
        y = find(parent, v)
 
        if x != y:
            e = e + 1    
            result.append([u,v,w])
            union(parent, rank, x, y)             
 
    return result

V代表图中的点数，graph是图中边的列表，每一个元素包含三个值：(u, v, w)，代表一条从u到v的边，其权值为w。