Kruskal`sMST: to find a minimum spanning tree for a connected weighted graph # tests: kruskal(graph) # graph = {'vertices': ['A', 'B', 'C', 'D', 'E', 'F'], 'edges': set([(4, 'A', 'B'),(8, 'A', 'C'),(15, 'A', 'D'),(16, 'B', 'C'),(23, 'B', 'D'),(42, 'C', 'D'),]) # expected is: set([(15, 'A', 'D'), (4, 'A', 'B'), (8, 'A', 'C')])

Kruskal`sMST.py

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

# author : wzx, 2123409
# date: Dec 14, 2014
# kruskal : graph{vertices,edge}  -> set([weight,vertices])
# to find a minimum spanning tree for a connected weighted graph
# algorithm
# example: kruskal(graph)
# graph:(4, 'A', 'B'),(8, 'A', 'C'),(15, 'A', 'D'),(16, 'B', 'C'),(23, 'B', 'D'),(42, 'C', 'D')
# to produce ([(15, 'A', 'D'), (4, 'A', 'B'), (8, 'A', 'C')])

# def kruskal(graph):
# return Minimum Spanning Tree of a graph
# tests: kruskal(graph)
# graph = {'vertices': ['A', 'B', 'C', 'D', 'E', 'F'],   'edges': set([(4, 'A', 'B'),(8, 'A', 'C'),(15, 'A', 'D'),(16, 'B', 'C'),(23,   'B', 'D'),(42, 'C', 'D'),])
# expected is: set([(15, 'A', 'D'), (4, 'A', 'B'), (8, 'A', 'C')])


'''
    V is used to define Node set. (= vertices & its value)
    V = {'A':'A','B':'B','C':'C','D':'D'}
    When A and B are connected, V is changed to 
    V = {'A':'B','B':'B','C':'C','D':'D'}
    thus,any two points are connnected,their values are the same.
'''
V = dict()
'''
    R means Rank.
    Initial State:R = {'A':'0','B':'0','C':'0','D':'0' } 
    If one vertice is used to be the end of  connections,its value +1.
    Explain:This vertice is used to mark the present Connected Component.
'''
R = dict()

class algorithm():
    
    def __init__(self):
        pass
#initialize V & R
    def make_set(self,point):
        V[point] = point
        R[point] = 0
#find out the boss(marker) of the Connected Component.
    def find(self,point):
        if V[point] != point:
            V[point] = self.find(V[point])
        return V[point]
#Connect two Connected Components and choose a new boss.(marker)
    def union(self,point1,point2):
        r1 = self.find(point1)
        r2 = self.find(point2)
        if R[r1] > R[r2]:
            V[r2] = r1
        else:
            V[r1] = r2
            if R[r1] == R[r2]:
                R[r2] += 1
#How KRUSKAL works
    def kruskal(self,graph):
        for vertice in graph['vertices']:
            self.make_set(vertice)      #initialization
        MSTree = set()
        edges = list(graph['edges'])
        edges.sort()                    #sort edge lengths from lowest to highest
        for edge in edges:
            weight, vertice1, vertice2 = edge
            if self.find(vertice1) != self.find(vertice2):# not in the same Component
                self.union(vertice1, vertice2)
                MSTree.add(edge)
        return MSTree

if __name__=="__main__":
    graph = {
        'vertices': ['A', 'B', 'C', 'D', 'E'],
        'edges': set([
                      (4, 'A', 'B'),
                      (8, 'A', 'C'),
                      (15, 'A', 'D'),
                      (16, 'B', 'C'),
                      (23, 'B', 'D'),
                      (42, 'C', 'D'),
                      ])
    }  # use set(instead list) in edges`s value to remove duplication
    arith = algorithm()
    print arith.kruskal(graph)

'''
    Reference:
    1.《算法设计与分析》王晓东
    2.http://en.wikipedia.org/wiki/Kruskal's_algorithm
    3.https://github.com/qiwsir/algorithm/blob/master/kruskal_algorithm.md
'''