KRUSKAL’S ALGORITHM USING PYTHON

Well, if you are a computer science major or into any interdisciplinary subjects consisting of concepts of data structure then it’s inevitable to not understand the concept of Kruskal's algorithm.

USE:

Finding minimum spanning tree from the weighted graph.

Now, let's start from the very basics. In the first part, I will be explaining the algorithm conceptually so that you could understand it in a breeze.

PART 1:

Weighted graph

Step 1: Write edges in non-decreasing order according to their weights.

Edge Weight
(b,c) — 1
(a,c) — 2
(a,b) — 2
(e,d) — 3
(a,e) — 4
(e,c) — 6
(d,c) — 7

Step 2: Start choosing edges in non-decreasing order such that chosen edge doesn’t form a circuit in the graph.

First (b,c) is chosen.
Then (a,c) is chosen since it doesn’t form a circuit.

Chosen edges

Now, (a,b) is discarded because it forms a circuit in the graph as shown below which is not acceptable for the minimum spanning tree.

Step 3: Continue the process until all vertices are included.

Using above process , after (b,c) and (a,c) ,

(e,d) and (a,e) are accepted. And the final graph is below:

This is the final graph obtained using Kruskal’s Algorithm.

PART 2:

Programmatically, it can be implemented in python as follow.

from typing import List # for annotations

class Edge :

def __init__(self, arg_src : int, arg_dst : int, arg_weight : int) :
self.src = arg_src
self.dst = arg_dst
self.weight = arg_weight

class Graph :

def __init__(self, num_nodes : int, edgelist : List[Edge]) :
self.num_nodes = num_nodes
self.edgelist = edgelist
self.parent = []
self.rank = []
# mst stores edges of the minimum spanning tree
self.mst = []

def FindParent (self, node : int) :
# With path-compression.
if node != self.parent[node] :
self.parent[node] = self.FindParent(self.parent[node])
return self.parent[node]

# Without path compression
# if node == self.parent[node] :
# return node
# return self.FindParent(self.parent[node])

def KruskalMST (self) :

# Sort objects of an Edge class based on attribute (weight)
self.edgelist.sort(key = lambda Edge : Edge.weight)

self.parent = [None] * self.num_nodes
self.rank = [None] * self.num_nodes

for n in range(self.num_nodes) :
self.parent[n] = n # Every node is the parent of itself at the beginning
self.rank[n] = 0 # Rank of every node is 0 at the beginning

for edge in self.edgelist :
root1 = self.FindParent(edge.src)
root2 = self.FindParent(edge.dst)

# Parents of the source and destination nodes are not in the same subset
# Add the edge to the spanning tree
if root1 != root2 :
self.mst.append(edge)
if self.rank[root1] < self.rank[root2] :
self.parent[root1] = root2
self.rank[root2] += 1
else :
self.parent[root2] = root1
self.rank[root1] += 1

print(“\nEdges of minimum spanning tree in graph :”, end=’ ‘)
cost = 0
for edge in self.mst :
print(“[“ + str(edge.src) + “-” + str(edge.dst) + “](“ + str(edge.weight) + “)”, end = ‘ ‘)
cost += edge.weight
print(“\nCost of minimum spanning tree : “ +str(cost))

def main() :

# Edge(source, destination, weight)
num_nodes = 6
e1 = Edge(0, 1, 4)
e2 = Edge(0, 2, 1)
e3 = Edge(0, 3, 5)
e4 = Edge(1, 3, 2)
e5 = Edge(1, 4, 3)
e6 = Edge(1, 5, 3)
e7 = Edge(2, 3, 2)
e8 = Edge(2, 4, 8)
e9 = Edge(3, 4, 1)
e10 = Edge(4, 5, 3)

g1 = Graph(num_nodes, [e1, e2, e3, e4, e5, e6, e7, e8, e9, e10])
g1.KruskalMST()

num_nodes = 7
a = Edge(0, 1, 1)
b = Edge(0, 2, 2)
c = Edge(0, 3, 1)
d = Edge(0, 4, 1)
e = Edge(0, 5, 2)
f = Edge(0, 6, 1)
g = Edge(1, 2, 2)
h = Edge(1, 6, 2)
i = Edge(2, 3, 1)
j = Edge(3, 4, 2)
k = Edge(4, 5, 2)
l = Edge(5, 6, 1)

g2 = Graph(num_nodes, [a, b, c, d, e, f, g, h, i, j, k, l])
g2.KruskalMST()

if __name__ == “__main__” :
main()

OUTPUT:

Code referenced from algotree.org

This is all about Kruskal’s Algorithm which a CS major might need to know for enhancing their ability in problem-solving capabilities in the domain of programming.

Thank you.