#问题

无向图最小生成树的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算法的计算过程，参与维基百科的词条：[普里姆算法](http://zh.wikipedia.org/wiki/%E6%99%AE%E6%9E%97%E5%A7%86%E7%AE%97%E6%B3%95)

将上述点与点关系以及两点之间距离（边长，有的文献中称之为权重）写成矩阵形式（在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）
	
	#! /usr/bin/env python
	#coding:utf-8
	
	from collections import defaultdict
	from heapq import *
	
	def prim( vertexs, edges ):
	    adjacent_vertex = defaultdict(list)      
        
        """
        注意：defaultdict(list)必须以list做为变量，可以详细阅读：[collections.defaultdict](https://docs.python.org/2/library/collections.html#collections.defaultdict)
	    """
	    for v1,v2,length in edges:
            adjacent_vertex[v1].append((length, v1, v2))
            adjacent_vertex[v2].append((length, v2, v1))

        """
	    经过上述操作，将edges列表中各项归类成以某点为dictionary的key，其value则是其相邻的点以及边长。如下：
	
	    defaultdict(<type 'list'>, {'A': [(7, 'A', 'B'), (5, 'A', 'D')], 
                                    'C': [(8, 'C', 'B'), (5, 'C', 'E')],