# 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 = []

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)

`Output:`
```The edges of the MST are :