Science Behind Clustering, Kruskal’s Algorithm

What is K-Clustering?

The process of combining related objects into clusters is known as clustering. A metric, such as a characteristic distance, is used to define similarity. Clustering can arrange the nearest nodes into k clusters given a collection of nodes and their distances from each other. Clustering photos that represent an object, grouping related webpages, and so on are some instances.

What is Kruskal’s algorithm?

It employs a greedy algorithm approach to discover the minimum spanning tree in a graph. The actual question is what is to be done after finding the minimum cost and where to use that gathered information and also where can it be useful to us.

Let’s take a real-life example where you are supposed to run multiple tasks at multiple places so you find the biggest road and the shortest distance to your destination which would make it the optimal route to travel. Kruskal’s algorithm has a similar job like this to help you find an optimal route for the same it would help you find the shortest route to the destination.

Working on Kruskal’s Algorithm

Kruskal’s is a part of the least difficult and straightforward algorithm where the decision is made based on the currently available evidence, without considering the long-term consequences of the current decision.

Greedy algorithm answers are assembled in parts, this methodology never re-examines previously made decisions. The greedy algorithm is not very difficult to execute and also is very effective in the majority of the cases.

Minimum Spanning Tree (MST)

It is a spanning tree subset of Chart G where all the vertices are covered with the minimum conceivable number of edges. As a result, a spanning tree lacks cycles and cannot be detached. This defines that we can reach an inference that is associated with each and an undirected Chart G which has any one of the spanning trees. When a chart is detached, there is no spanning tree, and also can’t be spread on all the vertices.

Kruskal’s work algorithm wise

Kruskal falls under the greedy algorithm which is its class and there is a local optimum which have the hopes of finding the global optimum. Here we start with the edges that have the least weightage and then continue to do the same until the objective arrives.

1) Sort all the edges from the low weight to high weightage.

2) Select the edge with the least amount of weight and add it to the spanning tree.

3) Continue to add edges until we’ve reached all of the vertices.

Applications of Minimum Spanning Tree Problems:

1- Network Design (telephone, electrical hydraulic, TV cable)

2- Approximation algorithms for NP-hard problems (traveling, salesperson, Steiner Tree)

3- Indirect application.

- Max bottleneck paths.

- LDPC codes for error correction.

- Image registration with Renyi Entropy.

- Reducing data storage in sequencing amino acids in a protein.

- Model of the locality of particle interactions in turbulent fluid flows.

Pseudo Code for Kruskal’s Algorithm

# 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
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
# A utility function for determining the set of an element
# (uses path compression technique)
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
# A function that performs the union of two sets of x and y values
# (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[2])
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)
# Else discard the edge
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)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
# Function call
g.KruskalMST()

With the above code we can see Kruskal Performance, With this, I would like to end My blog Thanks for Reading it Hope you learned something New.