Algoritmo para realizar un MST con el algoritmo de Prim. La construcción del grafo fue basada a partir del código compartido por K. Hong (https://plus.google.com/+KHongSanFrancisco)

MST_Prim.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math
import sys

class Graph:
    def __init__(self):
        self.size = 0
        self.vertices = { }

    def add_edge(self, frm, to, weight = 1):
        if self.vertices.has_key(frm) == False:
            print 'From vertex is not in the graph'
            quit()
        if self.vertices.has_key(to) == False:
            print 'To vertex %s is not in the graph' % (to)
            quit()
        self.vertices[frm].add_adjacent(self.vertices[to], weight)
        self.vertices[to].add_adjacent(self.vertices[frm], weight)

    def add_vertex(self, id):
        aux_vertex = Vertex(id)
        self.vertices[id] = aux_vertex
        self.size = self.size + 1

    def build_min_heap(self, queue):
        for i in range(int(math.floor(len(queue)/2)), -1, -1):
            self.min_heapify(queue, i)

    def heap_extract_min(self, queue):
        heap_size = len(queue)
        if heap_size < 1:
            print('Error: Heap underflow!')
            quit()
        min = queue[0]
        queue[0] = queue[heap_size - 1]
        queue.pop()
        self.min_heapify(queue, 0)
        return min

    def min_heapify(self, queue, index):
        aux_one = index
        queue_size = len(queue)
        while True:
            left_child  = (2 * aux_one) + 1
            right_child = (2 * aux_one) + 2
            if left_child < queue_size and self.vertices[queue[left_child]].key < self.vertices[queue[aux_one]].key:
                smallest = left_child
            else:
                smallest = aux_one
            if right_child < queue_size and self.vertices[queue[right_child]].key < self.vertices[queue[smallest]].key:
                smallest = right_child
            if smallest == aux_one:
                return
            aux_two = queue[aux_one]
            queue[aux_one] = queue[smallest]
            queue[smallest] = aux_two
            aux_one = smallest

    def MST_Prim(self, root):
        MST = [ ]
        queue = [ ]
        for vertex in self.vertices:
            queue.append(vertex)
        self.vertices[root].key = 0
        self.build_min_heap(queue)
        while len(queue) != 0:
            u_vertex = self.heap_extract_min(queue)
            if self.vertices[u_vertex].parent != None:
                aux_path = [graph.vertices[u_vertex].parent, graph.vertices[u_vertex].id]
                MST.append(aux_path)
            for adjacent in self.vertices[u_vertex].adjacent:
                if adjacent.id in queue and self.vertices[u_vertex].adjacent[adjacent] < adjacent.key:
                    adjacent.parent = u_vertex
                    adjacent.key = self.vertices[u_vertex].adjacent[adjacent]
            self.build_min_heap(queue)
        return MST

    def print_vertices(self):
        for vertex in self.vertices:
            print 'Vértice: ', vertex

    def print_adjacents(self, id):
        for vertex in self.vertices[id].adjacent:
            print 'Arista %s --> %s: ' %(id, vertex.id), self.vertices[id].adjacent[vertex]

class Vertex:
    def __init__(self, id):
        self.id = id
        self.key = sys.maxint
        self.parent = None
        self.adjacent = { }

    def add_adjacent(self, vertex, weight):
        self.adjacent[vertex] = weight

graph = Graph()

graph.add_vertex('a')
graph.add_vertex('b')
graph.add_vertex('c')
graph.add_vertex('d')
graph.add_vertex('e')
graph.add_vertex('f')
graph.add_vertex('g')
graph.add_vertex('h')
graph.add_vertex('i')

graph.add_edge('a', 'b', 4)
graph.add_edge('a', 'h', 8)

graph.add_edge('b', 'c', 8)
graph.add_edge('b', 'h', 11)

graph.add_edge('c', 'd', 7)
graph.add_edge('c', 'f', 4)
graph.add_edge('c', 'i', 2)

graph.add_edge('d', 'e', 9)
graph.add_edge('d', 'f', 14)

graph.add_edge('e', 'f', 10)

graph.add_edge('f', 'g', 2)

graph.add_edge('g', 'h', 1)
graph.add_edge('g', 'i', 6)

graph.add_edge('i', 'h', 7)

MST = graph.MST_Prim('a')
print MST