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

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.

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

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.Kruskal_MST()
``````

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