算法_Prim_Python

本文用到的包

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树