Day 45
Day 45: Kruskal's Algorithm
45/60 Days
Kruskal’s Algorithm #
Welcome to Day 45 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Kruskal’s Algorithm, another greedy algorithm used for finding the Minimum Spanning Tree (MST) of a weighted undirected graph.
What is Kruskal’s Algorithm? #
Kruskal’s Algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
How Kruskal’s Algorithm Works #
- Sort all the edges from low weight to high.
- Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
- Keep adding edges until we reach all vertices.
Implementation #
Let’s implement Kruskal’s Algorithm in Python:
1class DisjointSet:
2 def __init__(self, vertices):
3 self.parent = {v: v for v in vertices}
4 self.rank = {v: 0 for v in vertices}
5
6 def find(self, item):
7 if self.parent[item] != item:
8 self …
Continue Reading
Sign up or log in to access the full lesson and all 60 days of algorithm content.