DSA Tracker

Visualize

Minimum Spanning Tree (Kruskal's)

Sort edges by weight, union-find to skip anything that closes a cycle

time O(E log E)space O(V + E)

A spanning tree only needs n - 1 edges to connect every vertex with no cycle, and among every possible spanning tree Kruskal finds the lightest one with a simple greedy rule: sort all edges by weight, then walk them lightest first, accepting an edge only when its two endpoints are not already connected. Disjoint set union answers 'already connected?' in near constant time — each vertex tracks which component it belongs to, shown below as a badge, and two vertices sharing a badge means any edge between them would only close a cycle, so it gets skipped. The highlighted edges are the ones accepted into the tree so far.

Details

Animated on: 4 vertices, weighted undirected edges (0-1)=1, (0-2)=4, (1-2)=2, (1-3)=6, (2-3)=3 — find the minimum spanning tree's total weight using Kruskal's algorithm.

Problem:Minimum Spanning Tree (Kruskal's)Medium

Sort edges by weight, union-find to skip anything that closes a cycle

step 1 / 14

4 vertices, 5 weighted undirected edges

4 vertices and 5 weighted edges. The goal is not just any spanning tree but the one with the smallest total weight — Kruskal builds it by looking at edges lightest-first and taking any edge that does not close a cycle.

Pseudocode
1FUNCTION kruskalMST(n, edges):
2  SORT edges BY weight ASCENDING
3  parent[i] <- i FOR EACH i FROM 0 TO n - 1
4  mstWeight <- 0
5  count <- 0
6  FOR EACH (u, v, w) IN edges
7    IF FIND(u) != FIND(v)
8      UNION(u, v)
9      mstWeight <- mstWeight + w
10      count <- count + 1
11  RETURN mstWeight

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. 4 vertices and 5 weighted edges. The goal is not just any spanning tree but the one with the smallest total weight — Kruskal builds it by looking at edges lightest-first and taking any edge that does not close a cycle.
  2. Sort every edge by weight: (0,1)=1, (1,2)=2, (2,3)=3, (0,2)=4, (1,3)=6. Kruskal always considers the globally lightest remaining edge next, never just an edge touching the current tree.
  3. Each vertex starts as its own component: FIND(0)=0, FIND(1)=1, FIND(2)=2, FIND(3)=3. mstWeight <- 0, count <- 0.
  4. Next lightest edge is (0,1)=1. FIND(0)=0, FIND(1)=1 — different components, so this edge can only ever connect them, never close a loop.
  5. UNION(0,1) merges the two components. mstWeight <- 0 + 1 = 1, count <- 1.
  6. Next lightest edge is (1,2)=2. FIND(1)=0, FIND(2)=2 — different components, so this edge can only ever connect them, never close a loop.
  7. UNION(1,2) merges the two components. mstWeight <- 1 + 2 = 3, count <- 2.
  8. Next lightest edge is (2,3)=3. FIND(2)=0, FIND(3)=3 — different components, so this edge can only ever connect them, never close a loop.
  9. UNION(2,3) merges the two components. mstWeight <- 3 + 3 = 6, count <- 3.
  10. Next lightest edge is (0,2)=4. FIND(0)=0, FIND(2)=0 — already the SAME component, so this edge would close a cycle.
  11. Skip it — 0 and 2 are already connected through the tree so far, and adding this edge would only create a cycle without linking anything new. mstWeight stays 6.
  12. Next lightest edge is (1,3)=6. FIND(1)=0, FIND(3)=0 — already the SAME component, so this edge would close a cycle.
  13. Skip it — 1 and 3 are already connected through the tree so far, and adding this edge would only create a cycle without linking anything new. mstWeight stays 6.
  14. All 4 vertices sit in one component after 3 accepted edges (n - 1 = 3). RETURN mstWeight = 6.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Spanning Tree (Kruskal's) in the editorAll Graph problemsBack to roadmap