Kruskal’s Algorithm

It is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph.

Points to Remember:

• Sort all the edges (ascending order).
• Create union find for all ‘n’ node.
  • if no cycle, add to (uf).
  • if cycle, skip.
• Stop when MST has (n-1) edges.

Example 1:

Sorted Edges:

• 0 → 3, 1 ✅
• 0 → 1, 2 ✅
• 1 → 3, 3 ❌ Cycle (Skip)
• 1 → 2, 3 ✅
• 0 → 4, 4 ✅
• 3 → 2, 5 ❌ Cycle (Skip)
• 1 → 5, 7 ✅

There are no more edges to explore once you have obtained n−1 edges.

• MST Cost: 1 + 2 + 3 + 4 + 7 = 17

Example 2:

Sorted Edges:

• 1, 2 → 2
• 2, 5 → 2
• 2, 3 → 3
• 3, 4 → 3
• 4, 5 → 3
• 0, 2 → 4
• 0, 1 → 4
• 2, 4 → 4

Exploring Edges

• 1, 2 → 2

• 2, 5 → 2

• 2, 3 → 3

• 3, 4 → 3

• 4, 5 → 3
Cycle Detected (Skip)
• 0, 2 → 4

• 0, 1 → 4
Cycle Detected (Skip)
• 2, 4 → 4
Cycle Detected (Skip)

MST => 2 + 2 + 3 + 3 + 4 => 14