Loading algorithms…

Loading visualizer…

Algorithms/Graph/Kruskal's MST

Kruskal's MST

Greedy minimum spanning tree using Union-Find for cycle detection — O(E log E).

GraphMSTGreedyUnion-FindO(E log E)
Graph Visualization
MST edges: 0Cost: 0Skipped: 0
1 / 0
Speed
kruskal.js
1function kruskal(graph) {
2 const mst = [];
3 const uf = new UnionFind(graph.nodes);
4 
5 // Sort edges by weight, ascending
6 const sorted = [...graph.edges].sort(
7 (a, b) => a.weight - b.weight
8 );
9 
10 for (const edge of sorted) {
11 const { from, to } = edge;
12 
13 // Skip if both endpoints already connected
14 if (uf.find(from) === uf.find(to)) {
15 continue; // would form a cycle
16 }
17 
18 // Otherwise, merge the two components
19 uf.union(from, to);
20 mst.push(edge);
21 
22 // MST is complete when it has V-1 edges
23 if (mst.length === graph.nodes.length - 1) break;
24 }
25 
26 return { mst, totalCost: sum(mst.map(e => e.weight)) };
27}

Algorithm Explanation

Kruskal's algorithm builds a Minimum Spanning Tree (MST) by greedily adding the lightest edge that does not form a cycle. A spanning tree connects every node with the fewest possible edges (V−1), and "minimum" means the sum of edge weights is as small as possible.

⚙️ How It Works

  1. Sort edges by weight ascending — every step below just walks this list in order.
  2. Initialize a Union-Find data structure so every node starts in its own component.
  3. Walk the sorted edges. For each edge, ask:
    • Are its endpoints in the same component?
      → Adding it would form a cycle. Skip.
    • Otherwise: add the edge and merge the two components in Union-Find.
  4. Stop after V−1 edges have been added — the MST is complete.

🧩 Why Union-Find?

The naive "check if adding this edge creates a cycle" test is expensive. Union-Find (also called Disjoint Set Union) keeps each node's current component and supports two operations in near-constant time: find(node) and union(a, b). With path compression and union by rank, both run in amortized O(α(n)) time, where α is the inverse Ackermann function (effectively a constant for any practical input).

💡 Cut property: For any cut of the graph (a partition of nodes into two non-empty sets), the minimum-weight edge crossing that cut belongs to some MST. Kruskal repeatedly exploits this cut property by always adding the lightest edge that bridges two distinct components.

⚖️ Kruskal vs Prim's

Kruskal's (this page)
  • Sorts all edges up front — O(E log E).
  • Uses Union-Find for cycle detection.
  • Edge-centric — natural for sparse graphs.
  • Produces a Minimum Spanning Forest if the graph is disconnected.
Prim's
  • Grows one connected component from a seed — O(E log V).
  • Uses a priority queue keyed on minimum edge leaving the tree.
  • Node-centric — better on dense graphs.
  • Requires connectivity (or a super-source).
←Previous Algorithm
A* Search
GraphO(E log V)
Next Algorithm→
Prim's MST
O(E log V)Graph

Drag nodes to rearrange layout · Step through edges sorted by weight · Watch Union-Find track each component