#

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)

listtuple)

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

sortedlist.sort()listpythonsort),pythonheapq

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

        """
	    edgesdictionarykeyvalue
	
	    defaultdict(, {'A': [(7, 'A', 'B'), (5, 'A', 'D')], 
                                    'C': [(8, 'C', 'B'), (5, 'C', 'E')], 
                                    'B': [(7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E')], 
                                    'E': [(7, 'E', 'B'), (5, 'E', 'C'), (15, 'E', 'D'), (8, 'E', 'F'), (9, 'E', 'G')], 
                                    'D': [(5, 'D', 'A'), (9, 'D', 'B'), (15, 'D', 'E'), (6, 'D', 'F')], 
                                    'G': [(9, 'G', 'E'), (11, 'G', 'F')], 
                                    'F': [(6, 'F', 'D'), (8, 'F', 'E'), (11, 'F', 'G')]})
	
	    """
	
	    mst = []        #
	
	    chosed = set(vertexs[0]) 
	
	    """
	    vertexsvertexs = list("ABCDEFG")===>vertexs=['A', 'B', 'C', 'D', 'E', 'F', 'G']
	    >> chosed=set(vertexs[0])
	    >> chosed
	    set(['A'])
	    
	
	    """

        #adjacent_vertexs_edges'A'nodes[0]='A')listadjacent_vertexs['A']=[(7,'A','B'),(5,'A','D')]
	
	    adjacent_vertexs_edges = adjacent_vertex[vertexs[0]]  
	    
        #usable_edgesheappopheapqpython

	    heapify(adjacent_vertexs_edges)
	
	    while adjacent_vertexs_edges:
            #adjacent_vertexs_edges/
	        w, v1, v2 = heappop(adjacent_vertexs_edges)     
	        if v2 not in chosed:

                #used'A'A'D',5'd'used
	            chosed.add(v2)                          

	            mst.append((v1,v2,w))          #v1,v2,w('A','D',5) append into mst
	            
                #dheapheappush 

                for next_vertex in adjacent_vertex[v2]:                    
	                if next_vertex[2] not in chosed:
	                    heappush( adjacent_vertexs_edges,next_vertex)
	    return mst
	
	
	#test
	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 )

##

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