本文用到的包
from heapq import *
import networkx as nx
Prim算法用于在无向网络中找出一棵树。其精髓就是选一个初始节点，在网络上考虑扩散过程，不断地将节点添加到树中。Prim算法是可以找到最小权重树(minimum spanning tree)的，本处暂时不考虑考虑权重。如下网络
图1. 网络示意图
本网络在这里已经介绍，只需要在Python生成和Processing绘制时去掉方向即可。定义Prim函数如下
def prim(G, s):
P, Q = {}, [(0, None, s)]
while Q:
_, p, u = heappop(Q)
if u in P: continue
P[u] = p
for v, w in G[u].items():
heappush(Q, (1, u, v))
del P[s]
T=nx.DiGraph()
for i in P:
T.add_edge(P[i],i)
return T
测试：
T=prim(G, 0)
T.edges()
得到
[(0, 1), (1, 2), (1, 3), (2, 4), (2, 5), (2, 6)]
即
图2. Prim树
