Kruskal's Algorithm:
Finding the Minimum
Spanning Tree
Kruskal's Algorithm is a popular method for finding the minimum
spanning tree (MST) of a graph. The minimum spanning tree is a
subset of the edges that connect all the vertices in the graph
without any cycles and with the minimum possible total edge
weight.
GROUP 9 PRESENTATION
Steps for Kruskal's Algorithm
1 Sort the edges
Sort all the edges in non-decreasing order of their weights.
2 Initialize the forest
Start with a forest (a collection of trees), where each vertex is its own
tree.
3 Iterate through sorted edges
Pick the smallest edge from the sorted list. If it connects two different
trees, add it to the MST. If it connects vertices within the same tree,
skip it.
4 Repeat
Repeat this process until you've added enough edges to connect all the
vertices (i.e., the MST will have exactly V−1 edges, where V is the
number of vertices).
DIAGRAMATIC EXAMPLE What we will
do:
Keep including minimum edges as long they do not form
cycles
Wt = 2 + 2 + 1 + 1 + 4 + 6
= 16
Steps Applied on the Given Graph :
Sort the edges in ascending order of their
weights.
o From the image, the edges with their weights
are:
1. (f, g) = 1
2. (b, d) = 1
3. (a, b) = 2
4. (d, e) = 2
5. (g, c) = 6
6. (b, c) = 7
7. (b, f) = 8
8. (a, j) = 5
9. (j, i) = 4
10.(i, h) = 3
Step 2
Pick the smallest edge that does not form a cycle and add
it to the MST.
o (f, g) = 1 → Added ✅
o (b, d) = 1 → Added ✅
o (a, b) = 2 → Added ✅
o (d, e) = 2 → Added ✅
o (j, i) = 4 → Added ✅
o (g, c) = 6 → Added ✅
• We stop here because we have included (n-1) edges,
where n is the number of nodes.
Final MST and Its Weight:
1) The edges included in the MST:
(f, g), (b, d), (a, b), (d, e), (j, i), (g, c)
2) The total weight of the MST:
1 + 1 + 2 + 2 + 4 + 6 = 16
Python Implementation: Union-Find Data Structure
Disjoint Set Union (Union-Find) Explanation
The Union-Find data structure is used to efficiently track which vertices are
class UnionFind:
connected in the MST. The find() function determines the representative of
def __init__(self, n):
a set, and the union() function merges two sets if they are not already
self.parent = list(range(n))
connected.
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
Python Implementation: Kruskal's Algorithm
Kruskal's Algorithm Explanation
The kruskal() function implements Kruskal's Algorithm.
def kruskal(vertices, edges):
It sorts the edges by weight, iterates through them,
edges.sort(key=lambda x: x[2])
and uses the Union-Find data structure to determine if
uf = UnionFind(vertices)
adding an edge would create a cycle. If not, the edge is
mst = []
added to the MST.
mst_weight = 0
for u, v, weight in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append((u, v, weight))
mst_weight += weight
return mst, mst_weight
Example Usage
if __name__ == "__main__":
vertices = 5
edges = [
(0, 1, 4),
(0, 2, 3),
(1, 2, 2),
(1, 3, 5),
(2, 3, 6),
(3, 4, 7),
(0, 4, 8)
]
mst, mst_weight = kruskal(vertices, edges)
print("Edges in the MST:", mst)
print("Total weight of MST:", mst_weight)
This code demonstrates how to use Kruskal's Algorithm to find the MST of a
graph. The output shows the edges in the MST and the total weight of the
MST.
Example Output
Edges in the MST: [(1, 2, 2), (0, 2, 3), (1, 3, 5),
(3, 4, 7)]
Total weight of MST: 17
The output shows the edges in the MST and the total weight of the
MST. The MST is a subset of the edges that connects all the
vertices in the graph without any cycles and with the minimum
possible total edge weight.
Applications of Kruskal's Algorithm
Network Design: Kruskal's Algorithm Geographic Mapping: It can be used Circuit Design: Kruskal's Algorithm
can be used to design efficient to find the shortest paths between can be applied to design efficient
networks by finding the minimum locations on a map, minimizing the circuits by finding the minimum
spanning tree that connects all the total distance traveled. spanning tree that connects all the
nodes in the network. components in the circuit.
Key Takeaways
Kruskal's Algorithm is a powerful tool for finding the minimum
spanning tree of a graph. It is efficient, easy to implement, and has
numerous applications in various fields. Understanding the
algorithm and its implementation can be valuable for solving
problems related to network design, geographic mapping, and
circuit design.
THE END
