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)

    kruskal()

      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__init__(self,vertices):

                 self.V=vertices

                 self.graph=[]

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

                 self.graph.append([u,v,w])

             def find(self,parent,i):

                 if(parent[i]==i):

                     return i

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

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

                 xroot=self.find(parent,x)

                 yroot=self.find(parent,y)

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

                     parent[xroot] = yroot

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

                     parent[yroot] = xroot

                 else:

                     parent[yroot] = xroot

                     rank[xroot] += 1

             def KruskalMST(self):

                 result = []

                 i=0

                 e=0

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

                 parent,rank = [],[]

                 for node in range(self.V):

                     parent.append(node)

                     rank.append(0)

                 while(e < self.V-1):

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

                     i+=1

                     x = self.find(parent, u)

                     y = self.find(parent, v)

                     if(x != y):

                         e+=1

                         result.append([u,v,w])

                         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)

         g.addEdge(0,1,10)

         g.addEdge(0,2,6)

         g.addEdge(0,3,5)

         g.addEdge(1,3,15)

         g.addEdge(2,3,4)

 

         g.KruskalMST()     

 

    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.