Kruskal's Algorithm Visualizer

How it works

1. Sort all edges by weight, cheapest first.
2. Put every node in its own set: a forest of V one-node trees.
3. Take the next edge (u, v). If find(u) ≠ find(v), it joins two different trees: add it to the MST and union the two sets.
4. If find(u) = find(v), u and v are already connected, so the edge would close a cycle — skip it.
5. Stop once the MST has V − 1 edges. If the edges run out first, the graph is disconnected and the result is a minimum spanning forest.

Why the cheapest safe edge is always right

The proof rests on the cut property: split the nodes into any two groups, and the cheapest edge crossing between them belongs to some minimum spanning tree. When Kruskal accepts (u, v), look at the cut that separates u's current tree from everything else. Every cheaper edge has already been processed: those taken lie inside trees, and those skipped joined nodes of one tree, so none of them crosses this cut. (u, v) is the cheapest crossing edge, so taking it is safe.

The mirror image is the cycle property: the most expensive edge on any cycle is never needed, which is exactly the kind of edge Kruskal skips.

Worked example

The page opens on a 7-node graph whose 11 edges, sorted, are: B–C 1, E–G 1, A–C 2, D–F 2, D–E 3, A–B 4, B–D 5, F–G 6, C–D 8, B–E 9, C–F 10. Ties are broken alphabetically.

• Take B–C 1, E–G 1, A–C 2, D–F 2 and D–E 3 — each joins two different sets. Two trees remain: {A, B, C} and {D, E, F, G}.
• A–B 4: A and B are already in the same set, so this edge would close the triangle A–B–C. Skip it.
• B–D 5 joins the two trees. The MST now has 6 = V − 1 edges, so Kruskal stops without even looking at F–G, C–D, B–E or C–F.

Total weight: 1 + 1 + 2 + 2 + 3 + 5 = 14. In the visualizer each union-find set has its own colour, so you can watch the forest merge into one tree.

Union-find, the engine inside Kruskal

Union-find (a disjoint-set forest) keeps a parent pointer per node; the root of a node's tree identifies its set. Two small optimizations make it extremely fast: path compression (during find, point every visited node straight at the root) and union by size or rank (hang the smaller tree under the larger). Together they give an amortized cost of O(α(V)) per operation, where α is the inverse Ackermann function — at most 4 for any input that fits in the universe.

Without them a single find can take O(V), and checking cycles with a fresh DFS for every edge would make Kruskal O(E · V).

Kruskal vs Prim

• Same answer: both find a spanning tree of minimum total weight. When all weights are distinct the MST is unique; with ties they may pick different edges of equal total weight.
• Kruskal works globally on a sorted edge list and merges a forest. It is ideal for sparse graphs, for edges that arrive already sorted, and it produces a minimum spanning forest of a disconnected graph for free.
• Prim grows one tree from a start node using a priority queue of crossing edges: O(E log V) with a binary heap, or O(V²) with a plain array, which wins on dense graphs.
• Since E ≤ V², log E ≤ 2 log V, so O(E log E) and O(E log V) are the same class.

Common mistakes and uses

• Running it on a directed graph. MSTs are defined for undirected graphs; the directed version (minimum arborescence) needs the Chu–Liu/Edmonds algorithm.
• Not checking connectivity. If fewer than V − 1 edges were taken, there is no spanning tree.
• Worrying about negative weights. They are fine: only the relative order of the weights matters. For a maximum spanning tree, sort in descending order.

Uses: designing networks of cables, pipes or roads with minimum total length; single-linkage clustering (stop when k sets remain, which is the same as deleting the k − 1 heaviest MST edges); the MST-based 2-approximation for metric travelling salesman; and graph-based image segmentation.

Time and space complexity

Kruskal's Algorithm in Python

def kruskal(nodes, edges):
    """edges: [(u, v, w)] of an undirected graph. Returns (mst, total weight)."""
    edges = sorted(edges, key=lambda e: e[2])   # sort edges by weight (stable)
    parent = {v: v for v in nodes}              # each node is its own set
    size = {v: 1 for v in nodes}

    def find(x):                                # root of x's set
        if parent[x] != x:
            parent[x] = find(parent[x])         # path compression
        return parent[x]

    def union(a, b):                            # union by size
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    mst, total = [], 0
    for u, v, w in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            union(ru, rv)
            mst.append((u, v, w))               # take (u, v)
            total += w
        # else: skip - (u, v) would close a cycle
    return mst, total

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Prim's Algorithm VisualizerPrim's algorithm grows a minimum spanning tree from one node by always adding the cheapest edge leaving the tree. Watch it step by step, with heap-based code.
• Dijkstra's Algorithm VisualizerDijkstra's algorithm finds the shortest paths from one node in a graph with non-negative weights. Watch every relaxation step by step, with heap-based code.
• Sorting Algorithm VisualizerSorting algorithm visualizer: watch bubble, selection, insertion, shell, counting, radix, merge and quick sort step by step, then race them in Compare mode.
• Graph Algorithm VisualizerInteractive graph algorithm visualizer: draw or generate a graph and step through BFS, DFS, Dijkstra, Bellman-Ford, Kruskal, Prim, topological sort and SCCs.