Kruskal's Algorithm Calculator

Pseudocode

Sort every edge by weight, then walk the list adding any edge that joins two different components. Union-Find makes the "different components" test almost free.

Kruskal(graph):
    sort all edges by weight, ascending
    makeSet(v) for every vertex v
    mst = []

    for each edge (u, v, w) in sorted order:
        if find(u) != find(v):      // different components
            union(u, v)
            mst.append((u, v, w))
            if mst has V - 1 edges: break

    return mst

Kruskal grows a forest, not a tree. Several disconnected fragments develop independently and merge as cheap edges join them, which is the structural difference from Prim and the reason Kruskal handles disconnected graphs for free: it simply returns a minimum spanning forest. Correctness follows from the cut property applied to the component boundaries, exactly as with Prim.

Worked example, step by step

Build the minimum spanning tree on the same graph used for the Prim example, so the two orders of discovery can be compared.

Example graph: Undirected edges A-B (2), A-C (3), B-C (1), C-D (4) and B-D (7).

1. Sort the edges. By weight: B-C at 1, A-B at 2, A-C at 3, C-D at 4, B-D at 7. Every vertex starts in its own singleton set.
2. Accept B-C (1). B and C are in different sets, so the edge is accepted and the two merge. Components are now {B, C}, {A} and {D}.
3. Accept A-B (2). A and B are still in different sets, so accept and merge. Components are now {A, B, C} and {D}.
4. Reject A-C (3). A and C are now both in the same set, so this edge would close a cycle. It is skipped. This is the visible difference from Prim, which never even surfaced A-C as a candidate once both endpoints were in the tree.
5. Accept C-D (4). C and D are in different sets, so accept and merge. All four vertices are now in one component and the tree has three edges, so the algorithm can stop without examining B-D at 7.

The minimum spanning tree is B-C, A-B and C-D with total weight 1 + 2 + 4 = 7, identical to what Prim produced from A. The trees match, as they must when edge weights are distinct, but the discovery order differs: Prim went A-B, B-C, C-D growing outward from A, while Kruskal went B-C, A-B, C-D in pure weight order and had to explicitly reject a cycle-closing edge along the way.

Complexity, and where it comes from

Time: O(E log E) · Space: O(V + E)

Sorting the edges dominates everything else at O(E log E), which is the same as O(E log V) since E is at most V squared and so log E is within a constant factor of log V. After sorting, the loop performs at most 2E find operations and V - 1 unions. With both path compression and union by rank, each of those costs the inverse Ackermann function of V, which is below 5 for any input that fits in memory and is treated as constant. So the Union-Find part is effectively O(E) and the sort is the whole cost. When edges arrive already sorted, or can be bucketed because weights are small integers, Kruskal drops to near-linear and clearly beats Prim.

When to use Kruskal's MST Algorithm, and when not to

Kruskal and Prim solve the same problem. Density, edge ordering and connectivity decide which is better.

Common pitfalls

• Using Union-Find without path compression or union by rank. A naive implementation degenerates into linked lists and each find becomes O(V), pushing the loop to O(E·V). Both optimisations are a few lines each and are what make the near-constant bound real.
• Comparing vertices instead of set representatives. The cycle test is find(u) != find(v), not u != v. Comparing the vertices themselves accepts every edge and produces a graph full of cycles rather than a tree.
• Forgetting to stop at V - 1 edges. Not a correctness bug but a needless cost: once the tree has V - 1 edges it is complete and every remaining edge will be rejected. On a dense graph that is a large amount of wasted scanning.
• Assuming a unique answer with tied weights. When several edges share a weight, the sort order decides which are taken and different implementations produce different trees of equal total weight. Assert the total, not the edge set.
• Applying it to directed graphs. Like Prim, Kruskal is defined for undirected graphs. The directed analogue is the minimum spanning arborescence and needs the Chu-Liu/Edmonds algorithm.

Frequently asked questions

How does Kruskal's algorithm work?

It sorts every edge by weight and then walks the sorted list, adding an edge whenever its two endpoints lie in different components and skipping it when they are already connected. A Union-Find structure answers the connectivity question in near constant time. The result after V - 1 accepted edges is a minimum spanning tree.

What is the time complexity of Kruskal's algorithm?

O(E log E) time, dominated entirely by sorting the edges. The Union-Find operations add only O(E·α(V)), where α is the inverse Ackermann function and is effectively constant. If the edges are already sorted or can be bucket sorted, the algorithm becomes near-linear.

What is the difference between Kruskal's and Prim's algorithm?

Kruskal considers edges globally in weight order and grows a forest that merges into a tree, using Union-Find to reject cycles. Prim grows one connected tree outward from a start vertex using a priority queue. Kruskal suits sparse or pre-sorted graphs and handles disconnected input naturally; Prim suits dense graphs.

Why does Kruskal need Union-Find?

Because the only question it asks of each edge is whether its endpoints are already connected, and that question is asked E times. Union-Find answers it in near constant time with path compression and union by rank. Recomputing connectivity with a traversal for each edge would cost O(E·V) instead.

Can Kruskal handle a disconnected graph?

Yes, with no changes. It simply returns a minimum spanning forest, one tree per connected component, because it never requires the accepted edges to form a single connected structure while running. Prim, by contrast, stops once it exhausts the component containing its start vertex.