# 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.

## Leave a Reply