Kruskal Algorithm MST implementation in Python

By Prateek Kumar

Given module calculates the minimum cost of the spanning tree for a graph using Kruskal's algorithm. The graph is implemented by edge list and disjoint set union in Python.

Description of Graph class

attributes-

edgeLIst: List of list containg [vertex a, vertex b, weight]

parents: Python dictionary to store the set to which given vertex belongs

ranks: Python dictionary to store the number of element a set contains

 

methods-

addEdge(a,b,w): adds an undirected edge between vertex a and b having weight w

findSet(a): finds the set finds the main set to which element a belongs

unionSet(s1,s2): Union of two set s1 and s2 based on rank

kruskalMST(): Implementation of Kruskal's Algorithm