Uncover the Power of Kruskal's MST Algorithm with Python.

Minimum Spanning Tree use case.


A Spanning tree is a subset of a connected graph, where all the edges are connected and a tree must not have any cycle in it. A graph can have several different spanning trees. The weight of a spanning tree is equal to sum of weights of each edge of the spanning tree. So a minimum spanning tree (minimum weight spanning tree) for a weighted, connected, undirected graph is a spanning tree with a weight less than (or equal to) the weight of every other spanning tree.

Kruskal's Minimum Spanning Tree Algorithm.
Kruskal's Algorithm meme.

Python Knowledge Base: Make coding great again.
- Updated: 2024-12-20 by Andrey BRATUS, Senior Data Analyst.




    The steps for finding MST using Kruskal's algorithm are:

    - Sort all the edges from low weight to high (non-decreasing order).
    - Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then discard this edge.
    - Keep adding edges until all vertices are added.


  1. Kruskal's Minimum Spanning Tree Algorithm Python code:



  2. 
    from collections import defaultdict
     
    class Graph:
     
        def __init__(self, vertices):
            self.V = vertices  
            self.graph = []  
           
        # adding an edge to graph
        def addEdge(self, u, v, w):
            self.graph.append([u, v, w])
     
        # finding set of an element i
        def find(self, parent, i):
            if parent[i] == i:
                return i
            return self.find(parent, parent[i])
     
        # union of two sets
        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 Kruskal_MST(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 = i + 1
                x = self.find(parent, u)
                y = self.find(parent, v)
     
                if x != y:
                    e = e + 1
                    result.append([u, v, w])
                    self.union(parent, rank, x, y)
                 
            minimumCost = 0
            print ("Edges in MST")
            for u, v, weight in result:
                minimumCost += weight
                print("%d - %d = %d" % (u, v, weight))
            print("MST cost" , minimumCost)
     
    # Driver code
    g = Graph(4)
    g.addEdge(0, 1, 9)
    g.addEdge(1, 2, 6)
    g.addEdge(0, 3, 5)
    g.addEdge(1, 3, 15)
    g.addEdge(2, 3, 4)
     
    g.Kruskal_MST()
    
  3. Kruskal's Minimum Spanning Tree Algorithm code output:


  4. OUT: Edges in MST
    2 - 3 = 4
    0 - 3 = 5
    1 - 2 = 6
    MST cost 15





See also related topics: