本文用到的包
from heapq import *
import networkx as nx
Prim算法用于在無向網(wǎng)絡(luò)中找出一棵樹迈勋。其精髓就是選一個(gè)初始節(jié)點(diǎn)，在網(wǎng)絡(luò)上考慮擴(kuò)散過程躯砰，不斷地將節(jié)點(diǎn)添加到樹中辉阶。Prim算法是可以找到最小權(quán)重樹(minimum spanning tree)的，本處暫時(shí)不考慮考慮權(quán)重翔脱。如下網(wǎng)絡(luò)
圖1. 網(wǎng)絡(luò)示意圖
本網(wǎng)絡(luò)在這里已經(jīng)介紹奴拦，只需要在Python生成和Processing繪制時(shí)去掉方向即可。定義Prim函數(shù)如下
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
測(cè)試：
T=prim(G, 0)
T.edges()
得到
[(0, 1), (1, 2), (1, 3), (2, 4), (2, 5), (2, 6)]
即
圖2. Prim樹
