Kruskal's algorithm

Why it costs this much

Sorting the edges costs O(E log E), and each edge then needs two Union-Find operations, which are nearly constant.

Code

def kruskal(n, edges):                     # edges = [(w, u, v), ...]
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    total = 0
    for w, u, v in sorted(edges):          # O(E log E)
        ru, rv = find(u), find(v)
        if ru != rv:                       # near-constant work per edge
            parent[ru] = rv
            total += w
    return total

Common pitfalls

It needs Union-Find to detect cycles. On a disconnected graph it returns a spanning forest, not a tree.

Operation by operation

Kruskal minimum spanning tree. Sort edges, then use Union-Find. Sorting dominates. Union-Find needs O(V); a sorted copy of the edges needs O(E). O(E log E) equals O(E log V) because E is at most V².