最小生成树python代码

以下是Prim算法和Kruskal算法的Python代码实现，用于求解图的最小生成树：

# Prim算法
def prim(graph):
    # 初始化
    visited = set()
    unvisited = set(graph.keys())
    start = unvisited.pop()
    visited.add(start)
    heap = [(cost, start, end) for end, cost in graph[start].items()]
    heapq.heapify(heap)
    # 循环直到所有节点都被访问
    while unvisited:
        cost, start, end = heapq.heappop(heap)
        if end in visited:
            continue
        visited.add(end)
        unvisited.remove(end)
        for next_end, next_cost in graph[end].items():
            if next_end not in visited:
                heapq.heappush(heap, (next_cost, end, next_end))
    return visited

# Kruskal算法
def kruskal(graph):
    # 初始化
    edges = []
    for start, ends in graph.items():
        for end, cost in ends.items():
            edges.append((cost, start, end))
    edges.sort()
    parents = {node: node for node in graph.keys()}
    # 循环直到所有边都被访问
    for cost, start, end in edges:
        if find(parents, start) != find(parents, end):
            union(parents, start, end)
    return parents

def find(parents, node):
    if parents[node] != node:
        parents[node] = find(parents, parents[node])
    return parents[node]

def union(parents, node1, node2):
    parents[find(parents, node1)] = find(parents, node2)