如何用python实现最小生成树算法

在Python中实现最小生成树算法，常用的有两个库，一个是`networkx`库，它内置了Prim算法；另一个是`heapq`库结合自定义逻辑，实现Kruskal算法。这里分别简述一下这两种方法：

**使用`networkx`实现Prim算法**

import networkx as nx

def prim(graph, start):
    mst = nx.minimum_spanning_tree(graph, algorithm='prim')
    return list(mst.edges(data=True))

# 示例
graph = {'A': [ ('B', 5), ('D', 1) ],
         'B': [('C', 2)],
         'C': [('D', 3)],
         'D': []}
mst_edges = prim(nx.Graph(graph), 'A')  # 从'A'开始

**使用`heapq`实现Kruskal算法**

import heapq

def kruskal(graph):
    edges = [(weight, (u, v)) for u, v, weight in graph.edges.data('weight')]
    edges.sort()  # 按照权重升序排列
    mst = []
    visited = set()

    while len(visited) < len(graph):
        weight, (u, v) = heapq.heappop(edges)
        if u not in visited and v not in visited:
            mst.append((u, v))
            visited.add(u)
            visited.add(v)

    return mst

# 示例同上，只是将`prim(graph, 'A')`替换为 `kruskal(graph)`