- Prim算法利用最小生成树的MST性质，从边出发， 每次选择最小权重边，迭代进行。
2.见下例
幻灯片1.jpg
幻灯片2.jpg
幻灯片3.jpg
幻灯片4.jpg
幻灯片5.jpg
幻灯片6.jpg
幻灯片7.jpg
3.代码如下
Inf = float('inf')
def load_graph():
N=6
graph = [[0, 1, 12, Inf, Inf, Inf],
[1, 0, 9, 3, Inf, Inf],
[12, 9, 0, 4, 5, Inf],
[Inf, 3, 4, 0, 13, 15],
[Inf, Inf, 5, 13, 0, 4],
[Inf, Inf, Inf, 15, 4, 0]]
return graph,N
#返回最小代价的边
def locate_node(closedge):
chosen_node = -1
chosen_cost = Inf
for i,cost in enumerate(closedge):
if cost<chosen_cost and cost>0:
chosen_cost = cost
chosen_node = i
return chosen_node
def update_closedge(all_cost,V_U):
closedge = [Inf]*N
for node in V_U:
closedge[node]=all_cost[node]
return closedge
if __name__ == '__main__':
graph,N = load_graph()
#初始化值
node = 0
closedge = graph[0]
V_U = list(range(N))
V_U.remove(node)
edges = []
while len(V_U)!=0:
#选定最小权重边和下一个node节点
next_node = locate_node(closedge)
edges.append((node,next_node))
#更新closedge
closedge = update_closedge(graph[next_node],V_U)
#更新node
V_U.remove(next_node)
node = next_node
print(edges)
4.优缺点
- 优点：
适合于边多点少的稠密图
