Python Implementation of Kruskal Minimum Spanning Tree

Python Implementation of Kruskal Minimum Spanning Tree

Python Implementation of Kruskal Minimum Spanning Tree

    Kruskal's algorithm is a minimum spanning-tree algorithm which finds an edge of the least possible              weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it                  finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each              step.

    Minimum Spanning Tree :- Given a connected and undirected graph, a spanning tree       

                                of that graph is a subgraph that is a tree and connects all the vertices                                                         together. A single graph can have many different spanning trees.                                                                                                                                   A minimum spanning                                                                       tree (MST) or minimum weight spanning tree for a weighted,                                                                         connected and undirected graph is a spanning tree with weight                                                                     less than or equal to the weight of every other spanning tree.                                                                                                                                                    The weight of a                                                                 spanning tree is the sum of weights given to each edge of the                                                                       spanning tree.

     A minimum spanning tree has (V-1) edges where V is the number of vertices in the given graph.


    Steps to find Minimum Spanning Tree

  • Step 1 :-  Sort all the edges in non-decreasing order of their weight.
  • Step 2 :-  Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far                          using Union Find data-structure. If cycle is not formed, include this edge else, discard it.
  • Step 3 :-   Repeat Step 2 until there are (V-1) edges in the spanning tree.


    Pseudo-code for (MST)


      solve all edges in ascending order of their weight in an array e

      ans = 0

      for i = 1 to m

          v = e.first

          u = e.second

          w = e.weight

          if merge(u,v) //there will be no cycle

              then ans+=w


  Since,the algorithm is a Greedy Algorithm. The Greedy Choice is to pick the smallest weight edge              that does not cause a cycle in the MST constructed so far. Let us understand this algorithm with              an example, consider the below input graph.

    Code :-   from collections import defaultdict

         class Graph:




             def addEdge(self,u,v,w):


             def find(self,parent,i):


                     return i

                 return self.find(parent, parent[i])

             def union(self,parent,rank,x,y):



                 if(rank[xroot] < rank[yroot]):

                     parent[xroot] = yroot

                 elif(rank[xroot] > rank[yroot]):

                     parent[yroot] = xroot


                     parent[yroot] = xroot

                     rank[xroot] += 1

             def KruskalMST(self):

                 result = []



                 self.graph = sorted(self.graph,key=lambda item:item[2])

                 parent,rank = [],[]

                 for node in range(self.V):



                 while(e < self.V-1):

                     u,v,w = self.graph[i]


                     x = self.find(parent, u)

                     y = self.find(parent, v)

                     if(x != y):



                         self.union(parent, rank, x, y)

                 print("Following are the edges in the constructed MST")

                 for u,v,weight in result:

                     print("%d -- %d == %d" %(u,v,weight))


         g = Graph(4)









    Output :-    Following are the edges in the constructed MST

                       2 -- 3 == 4

                       0 -- 3 == 5

                       0 -- 1 == 10


   Complexity :- Worst time complexity  :- O(E*log V) using Union find.

                           Average time complexity :- O(E*log V) using Union find.

                                Best time complexity :- O(E*log V) using Union find.

                           Space complexity :- O(E + V)


    Application :-Minimum Spanning tree is used to describe/ design a network.

                           Image registration and segmentation (minimum spanning tree-based segmentation).                                                                                     Curvilinear feature extraction in computer vision.

                               Minimum spanning trees can also be used to describe financial markets.