## Python 3 Script Kruskal’s Minimum Spanning Tree Algorithm Full Example Project For Beginners Welcome folks today in this blog post we will be `implementing kruskal's minium spanning tree algorithm in python`. All the full source code of the application is shown below.

# Get Started

In order to get started you need to make an `app.py` file and copy paste the following code

`app.py`

``````# Python program for Kruskal's algorithm to find
# Minimum Spanning Tree of a given connected,
# undirected and weighted graph

from collections import defaultdict

# Class to represent a graph

class Graph:

def __init__(self, vertices):
self.V = vertices # No. of vertices
self.graph = [] # default dictionary
# to store graph

# function to add an edge to graph
self.graph.append([u, v, w])

# A utility function to find set of an element i
# (uses path compression technique)
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])

# A function that does union of two sets of x and y
# (uses union by rank)
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)

# Attach smaller rank tree under root of
# high rank tree (Union by Rank)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot

# If ranks are same, then make one as root
# and increment its rank by one
else:
parent[yroot] = xroot
rank[xroot] += 1

# The main function to construct MST using Kruskal's
# algorithm
def KruskalMST(self):

result = [] # This will store the resultant MST

# An index variable, used for sorted edges
i = 0

# An index variable, used for result[]
e = 0

# Step 1: Sort all the edges in
# non-decreasing order of their
# weight. If we are not allowed to change the
# given graph, we can create a copy of graph
self.graph = sorted(self.graph,
key=lambda item: item)

parent = []
rank = []

# Create V subsets with single elements
for node in range(self.V):
parent.append(node)
rank.append(0)

# Number of edges to be taken is equal to V-1
while e < self.V - 1:

# Step 2: Pick the smallest edge and increment
# the index for next iteration
u, v, w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent, v)

# If including this edge does't
# cause cycle, include it in result
# and increment the indexof result
# for next edge
if x != y:
e = e + 1
result.append([u, v, w])
self.union(parent, rank, x, y)

minimumCost = 0
print ("Edges in the constructed MST")
for u, v, weight in result:
minimumCost += weight
print("%d -- %d == %d" % (u, v, weight))
print("Minimum Spanning Tree" , minimumCost)

# Driver code
g = Graph(4)

# Function call
g.KruskalMST()

# This code is contributed by Neelam Yadav``````

See also  Python 3 Counting Sort Algorithm Script to Sort Strings Array Full Example Project For Beginners

Now if you execute the `python script` by typing the below command as shown below

`python app.py` 