问题

无向图最小生成树的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) 关于Prim算法的计算过程，参与维基百科的词条：普里姆算法 将上述点与点关系以及两点之间距离（边长，有的文献中称之为权重）写成矩阵形式（在list中，每两个点及其之间的距离组成一个tuple) 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)
] 在下面的解决方法中，要计算出与已经选出的若干个点有相邻关系的点中，相应边长最短的点。这本质上是排序之后取出最小的，因为这种排序是动态的，如果用sorted或者list.sort()之类的方法对list排序，一则速度慢（python中的sort方法对大数据时不是很快),二则代码也长了。幸好python提供了一个非常好用的模块：heapq。这个模块是堆排序方法实现排序，并能够随时取出最小值。简化代码，更重要是提升了速度。 就用这个来解决Prim算法问题了。

解决（Python）

  1.   1. #! /usr/bin/env python
  2.     2. #coding:utf-8
  3.     3.   4. from collections import defaultdict
  4.     5. from heapq import *
  5.     6.   7. def prim( vertexs, edges ):
  6.     8.     adjacent_vertex = defaultdict(list)      
  7.     9.   10.     """
  8.     11.     注意：defaultdict(list)必须以list做为变量，可以详细阅读：[collections.defaultdict](https://docs.python.org/2/library/collections.html#collections.defaultdict)
  9.     12.     """
  10.     13.     for v1,v2,length in edges:
  11.     14.         adjacent_vertex[v1].append((length, v1, v2))
  12.     15.         adjacent_vertex[v2].append((length, v2, v1))
  13.     16.   17.     """
  14.     18.     经过上述操作，将edges列表中各项归类成以某点为dictionary的key，其value则是其相邻的点以及边长。如下：
  15.     19.   20.     defaultdict(<type 'list'>, {'A': [(7, 'A', 'B'), (5, 'A', 'D')], 
  16.     21.                                 'C': [(8, 'C', 'B'), (5, 'C', 'E')], 
  17.     22.                                 'B': [(7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E')], 
  18.     23.                                 'E': [(7, 'E', 'B'), (5, 'E', 'C'), (15, 'E', 'D'), (8, 'E', 'F'), (9, 'E', 'G')], 
  19.     24.                                 'D': [(5, 'D', 'A'), (9, 'D', 'B'), (15, 'D', 'E'), (6, 'D', 'F')], 
  20.     25.                                 'G': [(9, 'G', 'E'), (11, 'G', 'F')], 
  21.     26.                                 'F': [(6, 'F', 'D'), (8, 'F', 'E'), (11, 'F', 'G')]})
  22.     27.   28.     """
  23.     29.   30.     mst = []        #存储最小生成树结果
  24.     31.   32.     chosed = set(vertexs[0]) 
  25.     33.   34.     """
  26.     35.     vertexs是顶点列表，vertexs = list("ABCDEFG")===>vertexs=['A', 'B', 'C', 'D', 'E', 'F', 'G']
  27.     36.     >> chosed=set(vertexs[0])
  28.     37.     >> chosed
  29.     38.     set(['A'])
  30.     39.     也就是，首先选一个点（这个点是可以任意选的），以这个点为起点，找其相邻点，以及最短边长。
  31.     40.   41.     """
  32.     42.   43.     #得到adjacent_vertexs_edges中顶点是'A'（nodes[0]='A')的相邻点list，即adjacent_vertexs['A']=[(7,'A','B'),(5,'A','D')]
  33.     44.   45.     adjacent_vertexs_edges = adjacent_vertex[vertexs[0]]  
  34.     46.   47.     #将usable_edges加入到堆中，并能够实现用heappop从其中动态取出最小值。关于heapq模块功能，参考python官方文档
  35.     48.   49.     heapify(adjacent_vertexs_edges)
  36.     50.   51.     while adjacent_vertexs_edges:
  37.     52.         #得到某个定点（做为adjacent_vertexs_edges的键）与相邻点距离（相邻点和边长/距离做为该键的值）最小值，并同时从堆中清除。
  38.     53.         w, v1, v2 = heappop(adjacent_vertexs_edges)     
  39.     54.         if v2 not in chosed:
  40.     55.   56.             #在used中有第一选定的点'A'，上面得到了距离A点最近的点'D',举例是5。将'd'追加到used中
  41.     57.             chosed.add(v2)                          
  42.     58.   59.             mst.append((v1,v2,w))          #将v1,v2,w，第一次循环就是('A','D',5) append into mst
  43.     60.   61.             #再找与d相邻的点，如果没有在heap中，则应用heappush压入堆内，以加入排序行列 
  44.     62.   63.             for next_vertex in adjacent_vertex[v2]:                    
  45.     64.                 if next_vertex[2] not in chosed:
  46.     65.                     heappush( adjacent_vertexs_edges,next_vertex)
  47.     66.     return mst
  48.     67.   68.   69. #test
  49.     70. vertexs = list("ABCDEFG")
  50.     71. edges = [ ("A", "B", 7), ("A", "D", 5),
  51.     72.           ("B", "C", 8), ("B", "D", 9), 
  52.     73.           ("B", "E", 7), ("C", "E", 5),
  53.     74.           ("D", "E", 15), ("D", "F", 6),
  54.     75.           ("E", "F", 8), ("E", "G", 9),
  55.     76.           ("F", "G", 11)]
  56.     77.   78. print "edges:",edges
  57.     79. print "prim:", prim( vertexs, edges )

运行结果

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)] prim: [(‘A’, ‘D’, 5), (‘D’, ‘F’, 6), (‘A’, ‘B’, 7), (‘B’, ‘E’, 7), (‘E’, ‘C’, 5), (‘E’, ‘G’, 9)]

整理人：豆包AI助手