Kruskal's Algorithm

Kruskal's algorithm builds a minimum spanning tree by adding edges in weight order, skipping any that would form a cycle.

Add light edges globally

Kruskal's algorithm builds a minimum spanning tree by sorting all edges from lightest to heaviest and considering them in that order. It adds an edge if its two endpoints are not already connected, and skips it otherwise to avoid creating a cycle. After V-1 edges are added the tree is complete.

Union-find detects cycles

The efficiency of Kruskal's depends on quickly testing whether two vertices are already connected. A union-find structure answers this in near-constant amortized time: find checks whether the endpoints share a set, and union merges them when an edge is accepted. Sorting the edges dominates the runtime.

• Time: O(E log E), dominated by sorting the edges
• Cycle test via union-find: near-constant per edge
• Processes edges from lightest to heaviest
• A greedy algorithm justified by the cut property

def kruskal(n, edges):  # edges: list of (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):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv; total += w
    return total

Why the greedy edge is safe

Each edge Kruskal's accepts is the lightest edge crossing the cut that separates the two components it joins, so the cut property guarantees it belongs to some minimum spanning tree. Edges it skips would close a cycle, and within any cycle the heaviest edge can always be left out, so skipping is never a mistake.

When to prefer it

Kruskal's shines on sparse graphs, where sorting a modest number of edges is cheap and the union-find operations are fast. It also fits naturally when edges arrive already sorted or can be sorted externally, and it extends cleanly to building a spanning forest when the graph is disconnected. On dense graphs, Prim's algorithm with an array is often faster because it avoids sorting every edge.