大胡子

数据结构与算法系列之无向加权图的最小生成树算法-Prim算法

发表于

解决问题

本算法主要解决的是无向加权图中找出权值最小的最小生成树，关于什么是最小生成树等基本概念本文不介绍

问题

假设点A,B,C,D,E,F，两点之间有连线的，以及它们的距离分别是：(A-B:7),(A-D:5),(B-C:8),(B-D:9),(B-E:7),(C-E:5),(D-E:15),(D-F:6),(E-F:8),(E-G:9),(F-G:11)
那么首先通过图的邻接矩阵表示形式，如下：
edges = [ (“A”, “B”, 7), (“A”, “D”, 5), (“B”, “C”, 8), (“B”, “D”, 9), (“B”, “E”, 7), (“C”, “E”, 5), (“D”, “E”, 15), (“D”, “F”, 6), (“E”, “F”, 8), (“E”, “G”, 9), (“F”, “G”, 11) ]
求出最小生成树？

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#encoding=utf-8
from collections import defaultdict
from heapq import *
def prim(vertexs,edges):
    #创建一个一键多值的字典
    heaplist_adjacent = defaultdict(list)
    #将键为每个顶点的每条边放在列表值上
    for v1,v2,len in edges:
        heaplist_adjacent[v1].append((len,v1,v2))
        heaplist_adjacent[v2].append((len,v2,v1))
    #构造返回的最小生成树列表
    mst = []
    #将已经走过的顶点加入到一个集合中
    have_walk = set(vertexs[0])
    #将字典中第一个顶点的对应的列表放进要排序的list中
    edgescompare_list = heaplist_adjacent[vertexs[0]]
    #进行堆排序
    heapify(edgescompare_list)
    #只要排序的list中由元素
    while edgescompare_list:
        #弹出边的权值最小的那个
        len,v1,v2 = heappop(edgescompare_list)
        print (len,v1,v2)
        #如果不再已走过的顶点中
        if v2 not in have_walk:
            #将新的顶点加入已走过的集合中
            have_walk.add(v2)
            #将这条信息加入到最小生成树中
            mst.append((v1,v2,len))
            #接下来操作是将这个顶点的所有边加入到列表中进行排序，前提是不包括加入mst中的边
            for next_vertex in heaplist_adjacent[v2]:
                if next_vertex[2] not in have_walk:
                    heappush(edgescompare_list,next_vertex)
    return mst
vertexs = list("ABCDEFG")
edges = [ ("A", "B", 7), ("A", "D", 5),
          ("B", "C", 8), ("B", "D", 9),
          ("B", "E", 7), ("C", "E", 5),
          ("D", "E", 15), ("D", "F", 6),
          ("E", "F", 8), ("E", "G", 9),
          ("F", "G", 11)]
print "edges:",edges
print "prim:", prim(vertexs, edges)