Kruskal's MST

Sorts all edges by weight and accepts any edge that connects two different components (union-find detects cycles). Same MST cost as Prim, built edge-wise instead of node-wise.

Category

Graphs

Time complexity

O(E log E)

Space complexity

O(V)

Pseudocode

sort edges by weight
accept if components differ
reject if it closes a cycle
stop at n−1 edges

Reference implementation

for e in sorted(edges):
    if find(e.a) != find(e.b):
        union(e.a, e.b)
        mst.append(e)

Open the interactive Kruskal's MST visualisation →