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.

Coding: The Silent Symphony. - Updated: 2024-05-19 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.


Kruskal's Minimum Spanning Tree Algorithm Python code:




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()

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





See also related topics: