Kruskal's Algorithm

#How does it work?

A minimum spanning tree (MST) is a set of edges in a weighted, connected graph that links every node, contains no cycle and has the smallest possible total weight. With V nodes an MST has exactly V − 1 edges.

Kruskal's algorithm (1956) sorts the edges by weight and tries them from the lightest. An edge joins the tree if its ends aren't connected yet; if they already are, it would close a cycle and is skipped.

Union-Find (disjoint sets) answers "are the ends already connected?" quickly: every accepted edge merges two sets. Step by step the algorithm turns a forest of single nodes into one tree.

#Try it yourself

#Step by step

1. 01Sort all edges by weight, smallest first.
2. 02Start with every node in a set of its own.
3. 03If the next edge (u, v) connects two different sets, take it and merge the sets; otherwise skip it.
4. 04Stop once the tree has V − 1 edges.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

EDGES = [(1, 2, 4), (1, 3, 1), (2, 4, 5), (2, 5, 2), (3, 5, 2), (3, 6, 4), (4, 7, 3), (5, 7, 6), (6, 7, 1)]
N = 7

parent = list(range(N + 1))  # union-find over nodes 1..7


def find(x: int) -> int:
    while parent[x] != x:
        parent[x] = parent[parent[x]]  # path halving
        x = parent[x]
    return x


tree, total = [], 0
for a, b, w in sorted(EDGES, key=lambda e: (e[2], e[0], e[1])):  # lightest first
    ra, rb = find(a), find(b)
    if ra == rb:
        continue  # already connected: this edge would close a cycle
    parent[ra] = rb
    tree.append(f"{a}-{b}")
    total += w
    if len(tree) == N - 1:
        break

print(" ".join(tree))  # edges in the order they were taken
print(total)

#Complexity

Sorting dominates; the union-find operations are constant time in practice. If the edges are already sorted, or the weights are small integers (counting sort), Kruskal runs in almost linear time. It shines on sparse graphs (E ≈ V).

#When to use it?

"Connect every point at the lowest cost" problems such as network cabling, power and pipeline design, clustering (drop the heaviest MST edges to get groups), image segmentation and approximate solutions for the travelling salesman problem use MSTs.

#Practice

Log in to answer questions and save your progress.