实现最小生成树计算的Prim算法和Kruskal算法python

Prim算法实现：

import heapq

def prim(graph, start):
    visited = set([start])
    edges = [
        (cost, start, to)
        for to, cost in graph[start].items()
    ]
    heapq.heapify(edges)
    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            yield frm, to, cost
            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

Kruskal算法实现：

def kruskal(graph):
    parent = {}
    rank = {}
    edges = []
    result = []
    for frm in graph:
        for to, cost in graph[frm].items():
            edges.append((cost, frm, to))
    edges.sort()
    for node in graph:
        parent[node] = node
        rank[node] = 0
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]
    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            if rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root1] = root2
                if rank[root1] == rank[root2]:
                    rank[root2] += 1
    for cost, frm, to in edges:
        if find(frm) != find(to):
            union(frm, to)
            result.append((frm, to, cost))
    return result

这两段代码中，我们假设输入的图是一个字典，其键为节点，值是该节点到达其他节点的边的权重，也是一个字典。输出是一个生成树，以元组列表的形式表示，每个元组由两个节点和它们之间的距离组成。