问题

思路说明

假设点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算法的计算过程，参与维基百科的词条：

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。这个模块是堆排序方法实现排序，并能够随时取出最小值。简化代码，更重要是提升了速度。

解决（Python）

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)]