Hello coders!! In this article, we will be digging into Kruskal’s Algorithm and learn how to implement it in Python. Let us first understand what does it mean. This algorithm is used to create a minimum spanning tree from a weighted graph. Now, we will look into this topic in detail.
Kruskal’s algorithm for minimum spanning tree:
Kruskal’s Algorithm is implemented to create an MST from an undirected, weighted, and connected graph. The edges are sorted in ascending order of weights and added one by one till all the vertices are included in it. It is a Greedy Algorithm as the edges are chosen in increasing order of weights. No cycle is created in this algorithm.
- At first, we will sort the edges in ascending order of their weights.
- After this, select the edge having the minimum weight and add it to the MST. If an edge creates a cycle, we reject it.
- Repeat the above steps till we cover all the vertices.
Illustration of Kruskal’s Algorithm:
Let us take the following graph as an example:
Now, the edges in ascending order of their weights are:
- 0-2 : 5
- 3-4 : 7
- 0-1 : 8
- 1-2 : 9
- 2-4 : 10
- 1-3 : 11
Now, we will select the minimum weighted edge, i.e. 0-2, and add it to MST:
The next edge that we will add to our MST is edge 3-4:
Now, we will add the edge 0-1:
Now, we have the edge 1-2 next, however, we we add this edge then a cycle will be created. As a result, this edge will be rejected.
After adding the edge 2-4, the MST is complete, as all the vertices are now included.
Implementation of Kruskal’s Algorithm in Python:
class Graph:
def __init__(self, vertex):
self.V = vertex
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def search(self, parent, i):
if parent[i] == i:
return i
return self.search(parent, parent[i])
def apply_union(self, parent, rank, x, y):
xroot = self.search(parent, x)
yroot = self.search(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(self):
result = []
i, e = 0, 0
self.graph = sorted(self.graph, key=lambda item: item[2])
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.search(parent, u)
y = self.search(parent, v)
if x != y:
e = e + 1
result.append([u, v, w])
self.apply_union(parent, rank, x, y)
for u, v, weight in result:
print("Edge:",u, v,end =" ")
print("-",weight)
g = Graph(5)
g.add_edge(0, 1, 8)
g.add_edge(0, 2, 5)
g.add_edge(1, 2, 9)
g.add_edge(1, 3, 11)
g.add_edge(2, 3, 15)
g.add_edge(2, 4, 10)
g.add_edge(3, 4, 7)
g.kruskal()
Output:
Time complexity:
The time complexity Of Kruskal’s Algorithm is: O(E log V)
Advantages of Kruskal’s Algorithm:
- It is easy to implement
- It offers a good control over the resulting MST
Application of Kruskal’s Algorithm:
- Used to make electrical wiring layout
- Used to make LAN connection
- A network of pipes for drinking water or natural gas.
- Single-link Cluster.
Must Read
- Understanding Python Bubble Sort with examples
- Top 10 Algorithms for Data Science
- Tower of Hanoi Implementation in Python
- 10 Machine Learning Algorithms for beginners
- Pigeonhole Sort in Python With Algorithm and Code Snippet
Conclusion:
This is all about Kruskal’s algorithm. We learned the algorithm in detail and also its implementation in python. WE also saw its advantages and its different applications in day to day needs.
However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.
Happy Pythoning!
very good work..
it helped us alot in making our assignment
Hi, is it possible to use if then statements in the kruskals code in python, for example “if 0-2:5 then 1-2:9”? if so how do you implement this into the code?
If you are talking about using only if then statements, then no you cannot implement the algorithm using it. The algorithm already has the if section inside the loop part.