205. Kruskal Minimum Spanning Tree

Why this mechanism works

Kruskal considers the cheapest remaining edge and accepts it only when it joins different components. DSU makes that cycle test efficient. The selected edges remain a forest, growing toward a spanning tree. Sorting determines which equal-cost optimum is returned.

State and boundaries

selected is an acyclic forest. DSU components are its connected components; total sums exactly its selected edge weights.

Protocol

1. Sort indexed edges by the specified key.
2. Start singleton components.
3. Accept an edge only when union succeeds.
4. Accumulate its weight and original tuple.
5. Stop after n-1 selections.
6. Return None if too few edges can be selected.

Visualization

0--1 weight 1; 1--2 weight 2; 0--2 weight 5
accept 1, accept 2 -> total 3
the heavier triangle edge is unnecessary

Python implementation

from kata_201 import DSU

def kruskal_mst(n, edges):
    if n == 0:
        return (0, [])
    ordered = sorted(enumerate(edges), key=lambda item:
                     (item[1][2], item[1][0], item[1][1], item[0]))
    dsu, selected, total = DSU(n), [], 0
    for _, (u, v, weight) in ordered:
        if dsu.union(u, v):
            selected.append((u, v, weight))
            total += weight
            if len(selected) == n - 1:
                break
    return (total, selected) if len(selected) == n - 1 else None

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 kruskal_mst: if n == 0:
n=3; edges=[(0, 2, 5), (1, 2, 2), (0, 1, 1)]

L7 <lambda>: (item[1][2], item[1][0], item[1][1], item[0]))
item=(0, (0, 2, 5))

L7 <lambda>: (item[1][2], item[1][0], item[1][1], item[0]))
item=(1, (1, 2, 2))

L7 <lambda>: (item[1][2], item[1][0], item[1][1], item[0]))
item=(2, (0, 1, 1))

L6 kruskal_mst: ordered = sorted(enumerate(edges), key=lambda item:
n=3; edges=[(0, 2, 5), (1, 2, 2), (0, 1, 1)]; ordered=[(2, (..., ..., ...)), (1, (..., ..., ...)), (0, (..., ..., ...))]

L8 kruskal_mst: dsu, selected, total = DSU(n), [], 0
n=3; edges=[(0, 2, 5), (1, 2, 2), (0, 1, 1)]; ordered=[(2, (..., ..., ...)), (1, (..., ..., ...)), (0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; selected=[]; total=0

L9 kruskal_mst: for _, (u, v, weight) in ordered:
n=3; edges=[(0, 2, 5), (1, 2, 2), (0, 1, 1)]; ordered=[(2, (..., ..., ...)), (1, (..., ..., ...)), (0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; selected=[]; total=0; _=2; u=0; v=1; weight=1

L10 kruskal_mst: if dsu.union(u, v):
n=3; edges=[(0, 2, 5), (1, 2, 2), (0, 1, 1)]; ordered=[(2, (..., ..., ...)), (1, (..., ..., ...)), (0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':2}; selected=[]; total=0; _=2; u=0; v=1; weight=1

... 2 intermediate state changes omitted ...

L9 kruskal_mst: for _, (u, v, weight) in ordered:
n=3; edges=[(0, 2, 5), (1, 2, 2), (0, 1, 1)]; ordered=[(2, (..., ..., ...)), (1, (..., ..., ...)), (0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':2}; selected=[(0, 1, 1)]; total=1; _=1; u=1; v=2; weight=2

L10 kruskal_mst: if dsu.union(u, v):
n=3; edges=[(0, 2, 5), (1, 2, 2), (0, 1, 1)]; ordered=[(2, (..., ..., ...)), (1, (..., ..., ...)), (0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':1}; selected=[(0, 1, 1)]; total=1; _=1; u=1; v=2; weight=2

L11 kruskal_mst: selected.append((u, v, weight))
n=3; edges=[(0, 2, 5), (1, 2, 2), (0, 1, 1)]; ordered=[(2, (..., ..., ...)), (1, (..., ..., ...)), (0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':1}; selected=[(0, 1, 1), (1, 2, 2)]; total=1; _=1; u=1; v=2; weight=2

L12 kruskal_mst: total += weight
n=3; edges=[(0, 2, 5), (1, 2, 2), (0, 1, 1)]; ordered=[(2, (..., ..., ...)), (1, (..., ..., ...)), (0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':1}; selected=[(0, 1, 1), (1, 2, 2)]; total=3; _=1; u=1; v=2; weight=2

L4 kruskal_mst: if n == 0:
n=3; edges=[(0, 1, 1)]

L7 <lambda>: (item[1][2], item[1][0], item[1][1], item[0]))
item=(0, (0, 1, 1))

L6 kruskal_mst: ordered = sorted(enumerate(edges), key=lambda item:
n=3; edges=[(0, 1, 1)]; ordered=[(0, (..., ..., ...))]

L8 kruskal_mst: dsu, selected, total = DSU(n), [], 0
n=3; edges=[(0, 1, 1)]; ordered=[(0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; selected=[]; total=0

L9 kruskal_mst: for _, (u, v, weight) in ordered:
n=3; edges=[(0, 1, 1)]; ordered=[(0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; selected=[]; total=0; _=0; u=0; v=1; weight=1

L10 kruskal_mst: if dsu.union(u, v):
n=3; edges=[(0, 1, 1)]; ordered=[(0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':2}; selected=[]; total=0; _=0; u=0; v=1; weight=1

L11 kruskal_mst: selected.append((u, v, weight))
n=3; edges=[(0, 1, 1)]; ordered=[(0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':2}; selected=[(0, 1, 1)]; total=0; _=0; u=0; v=1; weight=1

L12 kruskal_mst: total += weight
n=3; edges=[(0, 1, 1)]; ordered=[(0, (..., ..., ...))]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':2}; selected=[(0, 1, 1)]; total=1; _=0; u=0; v=1; weight=1

Why the solution is correct

For any accepted edge, its endpoints lie in different current components. It is a minimum-weight available edge crossing an appropriate component cut; the cut exchange argument shows it can belong to an optimum spanning tree extending the current forest. Repeating safe choices yields an MST when all vertices connect.

Time and space

O(E log E+V+E*alpha(V)) time and O(V+E) storage including sorting and output.

Common mistakes

Choosing the globally cheapest n-1 edges without cycle checks can leave vertices disconnected. Negative weights do not invalidate MST algorithms.

Reasoning card

Transfer exercise

Prove the cut exchange step by adding the chosen edge to an optimum tree and removing a no-cheaper edge from the resulting cycle.