Kruskal’s Minimum Spanning Tree Algorithm in Python

Welcome, in this blog I am going to demonstrate Kruskal’s Minimum spanning Tree Algorithm in Python. We use the greedy approach in this algorithm. Given a connected and undirected graph, a spanning tree of graph G is any subgraph of graph G that includes every vertex of graph G.

The cost of a spanning tree is the sum of the weights of all the included edges in the subgraph. There can be many spanning trees for a graph. The spanning tree that has the least cost is called the minimum spanning tree. There can also be many minimum spanning trees.

Kruskal’s Minimum Spanning Tree Algorithm Implementation

• Sort the edges of graph G in the increasing order of their weights.
• Start adding edges into the minimum spanning tree with the smallest weights which do not form a cycle, until (n-1) edges are added, where n is the number of vertices.
• Count the weight of all the added edges to find the cost of the minimum spanning tree.

class Graph:
    def __init__(self,n):
        self.vertices = n  #number of vertices
        self.graph = []

    def add_edge(self,from_vertice,to,weight):
        self.graph.append([from_vertice,to,weight])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent,parent[i])

    def union(self, parent, rank, a, b):
        a_root = self.find(parent, a)
        b_root = self.find(parent, b)
        if rank[a_root] < rank[b_root]:
            parent[a_root] = b_root
        elif rank[a_root] > rank[b_root]:
            parent[b_root] = a_root
        else: 
            parent[b_root] = a_root
            rank[a_root] += 1

    def KruskalAlgo(self):
        MST = []
        e = 0
        r = 0

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

        for node in range(self.vertices):
            parent.append(node)
            rank.append(0)

        while r < self.vertices - 1:
            from_vertice = self.graph[e][0]
            to = self.graph[e][1]
            weight = self.graph[e][2]
            e += 1
            a = self.find(parent, from_vertice)
            b = self.find(parent, to)

            if a != b:
                r += 1
                MST.append([from_vertice,to,weight])
                self.union(parent, rank, a, b)

        print("The edges of the MST are:")

        for from_vertice,to,weight in MST:
            print(from_vertice,to,weight)

G = Graph(6)

G.add_edge(0, 1, 2) 
G.add_edge(0, 3, 1) 
G.add_edge(0, 4, 4) 
G.add_edge(1, 2, 3) 
G.add_edge(1, 3, 3) 
G.add_edge(1, 5, 7) 
G.add_edge(2, 3, 5) 
G.add_edge(2, 5, 8) 
G.add_edge(3, 4, 9) 
  
G.KruskalAlgo() 

Output:

The edges of the MST are :
(0, 3, 1)
(0, 1, 2)
(1, 2, 3)
(0, 4, 4)
(1, 5, 7)

Thank You.