最小生成树 Prim算法

1. 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.优缺点

• 优点：
  适合于边多点少的稠密图