Chapter 38: DSA Kruskal’s Algorithm

DSA Kruskal’s Algorithm – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing the graph step by step, explaining every single detail slowly and clearly, showing exactly what happens in each step, and most importantly helping you understand why Kruskal’s algorithm is one of the most beautiful, most frequently asked, and most practical graph algorithms you will ever learn.

What is Kruskal’s Algorithm?

Kruskal’s algorithm finds the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph.

Minimum Spanning Tree means:

• A tree that connects all vertices
• Has no cycles
• Has the minimum possible total edge weight among all such spanning trees

Kruskal’s way of thinking is very simple and elegant:

“Sort all edges from cheapest to most expensive. Keep adding the next cheapest edge to our tree only if it does not create a cycle. Stop when we have connected all vertices.”

That’s it — it’s greedy, correct, and surprisingly easy to implement once you master Union-Find (Disjoint Set Union – DSU).

Why Kruskal’s Algorithm is Important

Real-world situations where Kruskal is used:

• Electrical / telecommunication network – connect all houses with minimum cable length
• Road / railway network – build cheapest connected road system between cities
• Computer network – connect routers/servers with minimum cable cost
• Clustering in machine learning – hierarchical clustering
• Approximation algorithms for NP-hard problems (like TSP)
• Image segmentation – group similar pixels with minimum cost

Important Properties of MST (must remember)

• Number of edges in MST = V − 1 (V = number of vertices)
• MST is always a tree (connected + acyclic)
• Graph can have multiple MSTs (if several edge sets have same total weight)
• MST exists only if graph is connected (otherwise → Minimum Spanning Forest)

Kruskal’s Algorithm Step-by-Step (very detailed)

Input:

• Undirected, weighted graph
• Vertices numbered 0 to V-1
• Edges with weights

Steps:

1. Sort all edges in non-decreasing order of weight
2. Initialize Union-Find – each vertex is its own component
3. Initialize empty MST list
4. For each edge in sorted order:
   • If the two vertices are not in the same component (no cycle):
     • Add this edge to MST
     • Union the two components
5. Stop when MST has V−1 edges or no more edges left

Classic Example Graph (we’ll solve step-by-step)

Vertices: 0, 1, 2, 3, 4, 5

Edges with weights:

• 0-1 : 4
• 0-2 : 2
• 1-2 : 1
• 1-3 : 5
• 2-3 : 8
• 2-4 : 10
• 3-4 : 2
• 3-5 : 6
• 4-5 : 3

Visual (imagine this on whiteboard):

Step 1: Sort edges by weight

Sorted list:

1. 1-2 : 1
2. 0-2 : 2
3. 3-4 : 2
4. 4-5 : 3
5. 0-1 : 4
6. 1-3 : 5
7. 3-5 : 6
8. 2-3 : 8
9. 2-4 : 10

Step 2: Start with 6 components (each vertex alone)

Step 3: Add edges one by one

• Add 1-2 (weight 1) → connect 1 & 2 MST edges: 1-2 Components: {0}, {1,2}, {3}, {4}, {5}
• Add 0-2 (weight 2) → connect 0 & {1,2} MST: 1-2, 0-2 Components: {0,1,2}, {3}, {4}, {5}
• Add 3-4 (weight 2) → connect 3 & 4 MST: 1-2, 0-2, 3-4 Components: {0,1,2}, {3,4}, {5}
• Add 4-5 (weight 3) → connect {3,4} & 5 MST: 1-2, 0-2, 3-4, 4-5 Components: {0,1,2}, {3,4,5}
• Add 0-1 (weight 4) → 0 & 1 already connected → skip (cycle)
• Add 1-3 (weight 5) → connect {0,1,2} & {3,4,5} MST: 1-2, 0-2, 3-4, 4-5, 1-3 Total weight = 1 + 2 + 2 + 3 + 5 = 13All vertices connected → stop

Final MST edges: 1-2(1), 0-2(2), 3-4(2), 4-5(3), 1-3(5)

Kruskal’s Algorithm Code (most common interview style)

Kruskal vs Prim – Very Important Interview Comparison

Rule of thumb (very common interview answer):

“I will choose Kruskal when the graph is sparse (E << V²) or when Union-Find is already implemented. I will choose Prim when the graph is dense or when we want to grow from a specific starting vertex.”

Summary – Kruskal’s Algorithm in one line each

• Finds Minimum Spanning Tree by sorting edges and adding them if no cycle
• Uses Union-Find to detect cycles efficiently
• Time complexity: O(E log E) ≈ O(E log V)
• Works on connected, undirected, weighted graphs with non-negative weights
• One of the two classic MST algorithms (along with Prim)
• Very frequently asked in medium/hard graph problems
• Real-world use: network design, clustering, circuit design, etc.

Would you like to go deeper into Kruskal or related topics?

Very natural next steps:

• Kruskal full step-by-step dry run with Union-Find changes
• Kruskal vs Prim – detailed comparison on same graph
• How Union-Find works with path compression & union by rank
• Handling disconnected graph (Minimum Spanning Forest)
• Applications of MST (real problems + interview questions)
• Bottleneck shortest path using MST

Just tell me which direction you want to go next — I’ll explain it in the same detailed, step-by-step, human-teacher style with clear examples and visuals! 😊