GeeksforGeeks Medium

MST — Kruskal's Algorithm

Build a minimum spanning tree by taking edges cheapest-first, skipping any that would close a cycle.

graphmstgreedyunion-find

02

Intuition

💡

Sort every edge by weight and walk the list, taking an edge whenever its endpoints are not already connected. Unlike Prim's, the partial result is a forest of separate trees that gradually merge. The only hard question — 'are these two vertices already connected?' — is exactly what Union-Find answers in near-constant time.

03

Approach

1

Sort edges by weight

Cheapest first. This is the greedy order, and the sort dominates the runtime at O(E log E).

2

Union-Find as the cycle test

find(u) == find(v) means both are already in the same tree, so the edge would create a cycle — skip it. Otherwise union them and take the edge.

3

Stop at V−1 edges

A spanning tree on V vertices has exactly V−1 edges. Finishing with fewer means the graph was disconnected and no spanning tree exists.

04

Solution & live demo

python

▶1def kruskal(n, edges):
▶2    parent = list(range(n))
▶3    def find(x):
▶4        while parent[x] != x:
▶5            parent[x] = parent[parent[x]]   # path compression
▶6            x = parent[x]
▶7        return x
▶8 
▶9    total, used = 0, 0
▶10    for u, v, w in sorted(edges, key=lambda e: e[2]):  # cheapest first
▶11        ru, rv = find(u), find(v)
▶12        if ru == rv:              # same component -> cycle
▶13            continue
▶14        parent[ru] = rv           # merge, take the edge
▶15        total += w
▶16        used += 1
▶17        if used == n - 1:
▶18            break
▶19    return total if used == n - 1 else None

05

Edge cases

Disconnected graph

Fewer than V−1 edges are taken — report no MST.

Duplicate weights

Any consistent tie-break works; different MSTs may result, all of equal weight.

Self-loop

Endpoints share a root immediately — always skipped.

06

Complexity

Time

O(E log E)

Space

O(V)

Sorting dominates; Union-Find is near-constant per query.