Kruskal's Algorithm
A greedy algorithm that finds a minimum spanning tree for a weighted undirected graph by adding edges in increasing order of weight.
Visualization
Details
Analogy
Imagine you are building a railway system to connect several cities, and you have a list of all possible tracks and their costs. Kruskal's algorithm is like starting with no tracks. You look at your list and build the absolute cheapest track possible between any two cities. Then you build the next cheapest track. You continue this, but you skip any track that would create a closed loop with the tracks you've already built. You stop once all cities are connected.
Purpose
To find a Minimum Spanning Tree (MST) by sorting all edges by weight and adding them to the tree if they don't form a cycle.
Use Cases
Network design, circuit design, and clustering. It is conceptually simple and can be more efficient than Prim's algorithm on sparse graphs.
Algorithm Steps
sort all edges by weight ascending
initialize union-find (disjoint set)
for each edge (u, v) in sorted order:
if find(u) != find(v):
add edge to MST
union(u, v)
if MST has V-1 edges: break
return MST
Explanation
What's Happening?
Sort all edges by weight. The cheapest edges are (A-D) and (C-E), both with weight 5.
Code Implementation
def kruskal(edges, num_vertices):
parent = list(range(num_vertices))
def find(i):
if parent[i] == i:
return i
parent[i] = find(parent[i])
return parent[i]
def union(i, j):
root_i = find(i)
root_j = find(j)
if root_i != root_j:
parent[root_i] = root_j
return True
return False
mst = []
edges.sort(key=lambda item: item[2])
for u, v, weight in edges:
if union(u, v):
mst.append((u, v, weight))
return mst