Kruskal's Algorithm — Finding the Minimum Spanning Tree

If you've ever wondered how Google Maps finds the most efficient route to connect multiple places, or how internet routers decide the cheapest network path — you've already touched on the problem Kruskal's Algorithm solves. It's one of the most elegant greedy algorithms in computer science, and once you understand it, graph problems start feeling a lot less intimidating.

Let's break it down — simply, visually, and completely.

What Problem Does It Solve?

Imagine you're a city planner. You have 5 cities and a list of possible roads between them, each road with a construction cost. Your goal: connect all 5 cities using the minimum total cost, without creating any loops (because loops waste money — you don't need two paths between the same two cities).

What you're trying to build is called a Minimum Spanning Tree (MST).

Kruskal's Algorithm is one of the most popular ways to find this MST. It was published by Joseph Kruskal in 1956 and is a classic example of a greedy algorithm — it makes the locally optimal choice at each step, and this guarantees a globally optimal result.

The Core Idea in One Line

Sort all edges by weight. Keep picking the smallest one — unless it creates a cycle.

That's Kruskal's in its purest form. Now let's see exactly how it works.

The Algorithm — Step by Step

1. Sort all edges of the graph in non-decreasing order of weight.
2. Initialize a disjoint set (Union-Find) — each vertex starts as its own component.
3. Iterate through sorted edges. For each edge:
   • If the two vertices belong to different components → add the edge to the MST and merge the components.
   • If they belong to the same component → skip (adding it would create a cycle).
4. Stop when the MST has exactly V−1 edges (where V = number of vertices).

Graph Example — Let's Walk Through It

Let's take a graph with 5 vertices (A, B, C, D, E) and 7 edges. Here's the original weighted graph:

The 7 edges with their weights:

After sorting by weight: A–B(2) → B–C(3) → B–E(5) → A–D(6) → C–E(7) → B–D(8) → D–E(9)

Step-by-Step Walkthrough

Step 1 — Pick A–B (weight 2)

A and B are in different components. Add it. No cycle formed.

MST edges so far: A–B | Total weight: 2

Step 2 — Pick B–C (weight 3)

B and C are in different components. Add it. No cycle.

MST edges so far: A–B, B–C | Total weight: 5

Step 3 — Pick B–E (weight 5)

B and E are in different components. Add it.

MST edges so far: A–B, B–C, B–E | Total weight: 10

Step 4 — Pick A–D (weight 6)

A and D are in different components. Add it.

MST edges so far: A–B, B–C, B–E, A–D | Total weight: 16

We now have 4 edges for 5 vertices — that's exactly V−1 = 4. The MST is complete!

The Secret Weapon: Union-Find

The key operation in Kruskal's is cycle detection — knowing whether two vertices are already connected. This is handled efficiently by a data structure called Union-Find (also called Disjoint Set Union or DSU).

It has two core operations:

• Find(x) — returns the "root" or representative of x's component.
• Union(x, y) — merges the components of x and y.

If Find(u) == Find(v) for an edge u–v, they're already in the same component — adding this edge would form a cycle. So we skip it.

Pseudocode

KRUSKAL(Graph G):
  MST = empty set
  Sort all edges E by weight (ascending)

  For each vertex v in G:
    MAKE-SET(v)   // each vertex is its own component

  For each edge (u, v, weight) in sorted E:
    if FIND(u) ≠ FIND(v):
      add (u, v) to MST
      UNION(u, v)
    if |MST| == V - 1:
      break

  return MST

Python Implementation

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []  # (weight, u, v)

    def add_edge(self, u, v, weight):
        self.edges.append((weight, u, v))

    def find(self, parent, x):
        if parent[x] != x:
            parent[x] = self.find(parent, parent[x])  # path compression
        return parent[x]

    def union(self, parent, rank, x, y):
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)

        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

    def kruskal_mst(self):
        self.edges.sort()  # sort by weight
        parent = list(range(self.V))
        rank = [0] * self.V

        mst = []
        total_weight = 0

        for weight, u, v in self.edges:
            if self.find(parent, u) != self.find(parent, v):
                self.union(parent, rank, u, v)
                mst.append((u, v, weight))
                total_weight += weight

            if len(mst) == self.V - 1:
                break

        return mst, total_weight


# ─── Example Usage ────────────────────────────────────────────
# Vertices: 0=A, 1=B, 2=C, 3=D, 4=E
g = Graph(5)
g.add_edge(0, 1, 2)  # A–B
g.add_edge(1, 2, 3)  # B–C
g.add_edge(1, 4, 5)  # B–E
g.add_edge(0, 3, 6)  # A–D
g.add_edge(2, 4, 7)  # C–E
g.add_edge(1, 3, 8)  # B–D
g.add_edge(3, 4, 9)  # D–E

mst, cost = g.kruskal_mst()
labels = {0: 'A', 1: 'B', 2: 'C', 3: 'D', 4: 'E'}

print("MST Edges:")
for u, v, w in mst:
    print(f"  {labels[u]} — {labels[v]}  (weight {w})")
print(f"\nTotal MST Weight: {cost}")

Output:

MST Edges:
  A — B  (weight 2)
  B — C  (weight 3)
  B — E  (weight 5)
  A — D  (weight 6)

Total MST Weight: 16

Time & Space Complexity

α(V) is the inverse Ackermann function — it grows so slowly that it's effectively constant for any real-world graph size. So Union-Find is essentially O(1) per operation in practice.

Kruskal's vs Prim's — Which Should You Use?

Both produce a valid MST for connected graphs. Kruskal's is often the simpler one to implement and reason about — which is why it's the more popular choice in interviews and competitive programming.

Where Is This Used in Real Life?

• Network design — laying cables, fiber, or pipelines to connect cities or buildings at minimum cost.
• Cluster analysis — building MSTs is a step in single-linkage clustering for grouping data points.
• Approximation algorithms — the MST is used as a subroutine in the 2-approximation for the Travelling Salesman Problem.
• Image segmentation — in computer vision, MSTs help identify boundaries between regions.
• Electrical circuit design — minimizing the wire length to connect components on a PCB.

Quick Recap

• Kruskal's finds the Minimum Spanning Tree of a weighted, undirected graph.
• It's a greedy algorithm — always picks the cheapest edge that doesn't create a cycle.
• Cycle detection uses Union-Find (path compression + union by rank).
• Time complexity is O(E log E), dominated by edge sorting.
• Best suited for sparse graphs. For dense graphs, consider Prim's.
• Result: V−1 edges that connect all vertices with minimum total weight.

Kruskal's is one of those algorithms that feels almost too simple to be correct — sort, iterate, skip cycles. But that elegance is exactly what makes greedy algorithms so satisfying. Once you understand the Union-Find underneath, the whole thing clicks into place.