Kruskal's Algorithm

Kruskal’s algorithm builds a minimum spanning tree by considering edges from cheapest to most expensive.

It uses Union-Find to avoid creating cycles.

Core Idea

Sort all edges by weight. For each edge, add it if it connects two different components. Skip it if both endpoints are already connected.

The greedy choice is safe because the cheapest edge connecting separate components can be part of a minimum spanning tree.

Python Example

def kruskal(vertex_count, edges, union_find):
    total = 0
    chosen = []
 
    for weight, a, b in sorted(edges):
        if union_find.union(a, b):
            total += weight
            chosen.append((a, b, weight))
            if len(chosen) == vertex_count - 1:
                break
 
    return total, chosen

The union_find object must provide a union method that returns whether a merge happened.

Common Confusions

Kruskal is edge-centered. It does not grow from one start vertex.

Sorting dominates much of the cost. The algorithm needs all candidate edges available or at least processable in weight order.

When To Use It

Use Kruskal when edges are easy to sort, the graph may be sparse, and Union-Find is a natural way to track connected components.