PK

PKBytes

Explore tracks
Chapter 36: Minimum Spanning Trees and Graph Connectivity
36.02Intermediate / Advanced4 topics14 min4 interactive animations

Kruskal's algorithm

Kruskal's algorithm sorts the edges by weight and adds each edge that joins two different components, using union-find to test; it runs in O(m log m) and handles disconnected graphs by returning a spanning forest.

Learning goals

  • Sort edges and process them lightest first
  • Use union-find to accept or reject each edge
  • Describe how the forest of components grows
  • Get a minimum spanning forest on a disconnected graph

Prerequisites

MST definitionsUnion-find

Kruskal's idea is the most direct one: look at the cheapest edge and take it unless it is useless. The cut property proves that this greedy choice is always safe.

36.02.1

Sort edges

Sort all edges by weight, smallest first. Java's Arrays.sort on objects is stable, so edges with equal weights stay in input order; with ties the resulting tree may differ between sorts, but the total weight never does. Sorting costs O(m log m) and dominates the running time.

To find a **maximum** spanning tree, sort heaviest first; nothing else changes. Step through the first animation option to see the sorted edge strip with each edge marked as taken or rejected.

Java
1static int[][] sortedEdges(int[][] edges) {                       // lightest first; equal weights keep their input order
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));
4    return sorted;
5}

Minimum spanning tree: Kruskal and Prim (lazy and eager)

Interactive · edit the input

Your input

Try

undirected graph · 6 vertices · 8 edges

0

C0

1

C1

2

C2

3

C3

4

C4

5

C5

Edge / vertex being consideredIn the treeRejected (would close a cycle)In the heap or frontier

edges, lightest first

1-2:1
1-3:2
0-2:3
0-1:4
2-3:4
2-4:5
4-5:6
3-4:7

component leader of v

00
11
22
33
44
55
Setup

Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.

Step 1 / 10
Java
1static long kruskal(int n, int[][] edges) {          // edges {u, v, w}; total weight of the minimum spanning forest
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));   // lightest first
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    long total = 0;
7    for (int[] e : sorted) {
8        int a = find(parent, e[0]), b = find(parent, e[1]);
9        if (a == b) continue;                           // already connected: this edge would close a cycle
10        parent[a] = b;
11        total += e[2];
12    }
13    return total;
14}
15static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
16static long primLazy(int n, List<int[]>[] adj, int s) {   // adj[u] = {v, w}; weight of the tree of s's component
17    boolean[] in = new boolean[n];
18    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);   // {vertex, weight of the edge that reaches it}
19    pq.add(new int[]{s, 0});
20    long total = 0;
21    while (!pq.isEmpty()) {
22        int[] top = pq.poll();
23        if (in[top[0]]) continue;                       // outdated: already in the tree
24        in[top[0]] = true;
25        total += top[1];
26        for (int[] e : adj[top[0]]) if (!in[e[0]]) pq.add(new int[]{e[0], e[1]});
27    }
28    return total;
29}
30static long primEager(int n, List<int[]>[] adj, int s) {   // key[v] = cheapest edge from the tree to v
31    long INF = Long.MAX_VALUE / 2;
32    long[] key = new long[n];
33    Arrays.fill(key, INF);
34    key[s] = 0;
35    boolean[] in = new boolean[n];
36    long total = 0;
37    for (int step = 0; step < n; step++) {
38        int u = -1;
39        for (int v = 0; v < n; v++) if (!in[v] && key[v] < INF && (u == -1 || key[v] < key[u])) u = v;
40        if (u == -1) break;                             // the rest is unreachable
41        in[u] = true;
42        total += key[u];
43        for (int[] e : adj[u]) if (!in[e[0]] && e[1] < key[e[0]]) key[e[0]] = e[1];   // decrease key
44    }
45    return total;
46}

Live state

0 edges examined0 edges rejected

n

6

edges

8

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L3n=6 edges=8Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.
2L11edge=1-2:1 total=11-2:1 joins two different components: add it to the tree. Total weight 1.
3L11edge=1-3:2 total=31-3:2 joins two different components: add it to the tree. Total weight 3.
4L11edge=0-2:3 total=60-2:3 joins two different components: add it to the tree. Total weight 6.
5L9edge=0-1:40-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6L9edge=2-3:42-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7L11edge=2-4:5 total=112-4:5 joins two different components: add it to the tree. Total weight 11.
8L11edge=4-5:6 total=174-5:6 joins two different components: add it to the tree. Total weight 17.
9L9edge=3-4:73-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10L13return=17 components=1The tree has 5 edges and total weight 17 (the smallest possible).
36.02.2

DSU

Kruskal asks, for every edge, *are these two ends already connected through the tree built so far?* A disjoint-set union answers in nearly constant time: find returns the representative of a component, and union merges two components. An edge is accepted only when the two representatives differ, and accepting it merges them.

Path compression and union by size make the cost per operation almost constant, so the whole algorithm is dominated by sorting. The union-find on edges animation shows components, the first redundant edge and Kruskal.

Java
1static class Dsu {
2    private final int[] parent, size;
3    int components;
4    Dsu(int n) {
5        parent = new int[n];
6        size = new int[n];
7        components = n;
8        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
9    }
10    int find(int x) {
11        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
12        return x;
13    }
14    boolean union(int a, int b) {                                  // false when a and b were already together
15        a = find(a);
16        b = find(b);
17        if (a == b) return false;
18        if (size[a] < size[b]) { int t = a; a = b; b = t; }        // attach the smaller tree under the larger
19        parent[b] = a;
20        size[a] += size[b];
21        components--;
22        return true;
23    }
24}

Union-find on edges: components, redundant edge, Kruskal

Interactive · edit the input

Your input

Try

disjoint-set forest (arrow = parent, roots on top) · 6 nodes

0
1
2
3
4
5
Edge kept (joins two sets)Edge skipped (same set)Edge being testedNot tested yetA root

edges in the order given

0-11
1-22
3-43
2-04
4-55
Setup

Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.

Step 1 / 7
Java
1int countComponents(int n, int[][] edges) {
2    DSU d = new DSU(n); int comps = n;
3    for (int[] e : edges) if (d.union(e[0], e[1])) comps--;       // a successful union merges two components
4    return comps;
5}
6int[] firstCycleEdge(int n, int[][] edges) {     // the first edge whose endpoints are already connected
7    DSU d = new DSU(n);
8    for (int[] e : edges) if (!d.union(e[0], e[1])) return e;
9    return null;
10}
11long kruskal(int n, int[][] edges) {             // edges are {a, b, w}
12    int[][] sorted = edges.clone();
13    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));      // stable: ties keep the input order
14    DSU d = new DSU(n); long total = 0;
15    for (int[] e : sorted) if (d.union(e[0], e[1])) total += e[2];   // keep an edge only if it joins two components
16    return total;
17}

Live state

0 edges kept0 edges skipped6 components

vertices

6

edges

5

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1vertices=6 edges=5Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.
2L3edge=0-1 components=5Edge 0-1 joins the sets of roots 0 and 1: 5 components left.
3L3edge=1-2 components=4Edge 1-2 joins the sets of roots 0 and 2: 4 components left.
4L3edge=3-4 components=3Edge 3-4 joins the sets of roots 3 and 4: 3 components left.
5L3edge=2-0 root of a=0 root of b=0Edge 2-0: both ends have root 0, so they are already connected. Skip it.
6L3edge=4-5 components=2Edge 4-5 joins the sets of roots 3 and 5: 2 components left.
7L4return=22 connected components (provinces). The edges kept form a spanning forest with 4 edges.
36.02.3

Forest growth

At the start there are n single-vertex trees. Each accepted edge joins two of them, so after k accepted edges there are n - k trees; the algorithm stops being able to accept anything once one tree remains. The picture is a **forest** whose trees merge, and the animation labels every vertex with its component leader.

Every accepted edge is the lightest edge leaving one of the two trees it joins (otherwise a lighter edge would have been processed and accepted earlier), which is the cut property applied to that tree. This is the proof sketch of correctness, expanded in the last lesson of the chapter.

Java
1static List<int[]> kruskalEdges(int n, int[][] edges) {             // the chosen edges in the order they are accepted
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    List<int[]> tree = new ArrayList<>();
7    for (int[] e : sorted) {
8        int a = find(parent, e[0]), b = find(parent, e[1]);
9        if (a == b) continue;                                       // already connected: this edge would close a cycle
10        parent[a] = b;
11        tree.add(e);
12        if (tree.size() == n - 1) break;                            // a spanning tree is complete
13    }
14    return tree;
15}
16static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

Minimum spanning tree: Kruskal and Prim (lazy and eager)

Interactive · edit the input

Your input

Try

undirected graph · 6 vertices · 8 edges

0

C0

1

C1

2

C2

3

C3

4

C4

5

C5

Edge / vertex being consideredIn the treeRejected (would close a cycle)In the heap or frontier

edges, lightest first

1-2:1
1-3:2
0-2:3
0-1:4
2-3:4
2-4:5
4-5:6
3-4:7

component leader of v

00
11
22
33
44
55
Setup

Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.

Step 1 / 10
Java
1static long kruskal(int n, int[][] edges) {          // edges {u, v, w}; total weight of the minimum spanning forest
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));   // lightest first
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    long total = 0;
7    for (int[] e : sorted) {
8        int a = find(parent, e[0]), b = find(parent, e[1]);
9        if (a == b) continue;                           // already connected: this edge would close a cycle
10        parent[a] = b;
11        total += e[2];
12    }
13    return total;
14}
15static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
16static long primLazy(int n, List<int[]>[] adj, int s) {   // adj[u] = {v, w}; weight of the tree of s's component
17    boolean[] in = new boolean[n];
18    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);   // {vertex, weight of the edge that reaches it}
19    pq.add(new int[]{s, 0});
20    long total = 0;
21    while (!pq.isEmpty()) {
22        int[] top = pq.poll();
23        if (in[top[0]]) continue;                       // outdated: already in the tree
24        in[top[0]] = true;
25        total += top[1];
26        for (int[] e : adj[top[0]]) if (!in[e[0]]) pq.add(new int[]{e[0], e[1]});
27    }
28    return total;
29}
30static long primEager(int n, List<int[]>[] adj, int s) {   // key[v] = cheapest edge from the tree to v
31    long INF = Long.MAX_VALUE / 2;
32    long[] key = new long[n];
33    Arrays.fill(key, INF);
34    key[s] = 0;
35    boolean[] in = new boolean[n];
36    long total = 0;
37    for (int step = 0; step < n; step++) {
38        int u = -1;
39        for (int v = 0; v < n; v++) if (!in[v] && key[v] < INF && (u == -1 || key[v] < key[u])) u = v;
40        if (u == -1) break;                             // the rest is unreachable
41        in[u] = true;
42        total += key[u];
43        for (int[] e : adj[u]) if (!in[e[0]] && e[1] < key[e[0]]) key[e[0]] = e[1];   // decrease key
44    }
45    return total;
46}

Live state

0 edges examined0 edges rejected

n

6

edges

8

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L3n=6 edges=8Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.
2L11edge=1-2:1 total=11-2:1 joins two different components: add it to the tree. Total weight 1.
3L11edge=1-3:2 total=31-3:2 joins two different components: add it to the tree. Total weight 3.
4L11edge=0-2:3 total=60-2:3 joins two different components: add it to the tree. Total weight 6.
5L9edge=0-1:40-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6L9edge=2-3:42-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7L11edge=2-4:5 total=112-4:5 joins two different components: add it to the tree. Total weight 11.
8L11edge=4-5:6 total=174-5:6 joins two different components: add it to the tree. Total weight 17.
9L9edge=3-4:73-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10L13return=17 components=1The tree has 5 edges and total weight 17 (the smallest possible).
36.02.4

Disconnected minimum spanning forest

If the graph is not connected, Kruskal needs no change: it accepts edges until none remains that joins two components, which leaves one tree per component, a **minimum spanning forest**. The number of trees is n - (accepted edges).

Be careful with the early exit tree.size() == n - 1: it never triggers on a disconnected graph, which is correct. Prim, in contrast, grows only the component of its start vertex, so for a forest it must be started once in each component. See the two disconnected presets.

Java
1static long[] forestSummary(int n, int[][] edges) {                 // {number of trees, edges chosen, total weight}
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    int chosen = 0;
7    long total = 0;
8    for (int[] e : sorted) {
9        int a = find(parent, e[0]), b = find(parent, e[1]);
10        if (a == b) continue;
11        parent[a] = b;
12        chosen++;
13        total += e[2];
14    }
15    return new long[]{n - chosen, chosen, total};
16}
17static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

Minimum spanning tree: Kruskal and Prim (lazy and eager)

Interactive · edit the input

Your input

Try

undirected graph · 6 vertices · 8 edges

0

C0

1

C1

2

C2

3

C3

4

C4

5

C5

Edge / vertex being consideredIn the treeRejected (would close a cycle)In the heap or frontier

edges, lightest first

1-2:1
1-3:2
0-2:3
0-1:4
2-3:4
2-4:5
4-5:6
3-4:7

component leader of v

00
11
22
33
44
55
Setup

Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.

Step 1 / 10
Java
1static long kruskal(int n, int[][] edges) {          // edges {u, v, w}; total weight of the minimum spanning forest
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));   // lightest first
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    long total = 0;
7    for (int[] e : sorted) {
8        int a = find(parent, e[0]), b = find(parent, e[1]);
9        if (a == b) continue;                           // already connected: this edge would close a cycle
10        parent[a] = b;
11        total += e[2];
12    }
13    return total;
14}
15static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
16static long primLazy(int n, List<int[]>[] adj, int s) {   // adj[u] = {v, w}; weight of the tree of s's component
17    boolean[] in = new boolean[n];
18    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);   // {vertex, weight of the edge that reaches it}
19    pq.add(new int[]{s, 0});
20    long total = 0;
21    while (!pq.isEmpty()) {
22        int[] top = pq.poll();
23        if (in[top[0]]) continue;                       // outdated: already in the tree
24        in[top[0]] = true;
25        total += top[1];
26        for (int[] e : adj[top[0]]) if (!in[e[0]]) pq.add(new int[]{e[0], e[1]});
27    }
28    return total;
29}
30static long primEager(int n, List<int[]>[] adj, int s) {   // key[v] = cheapest edge from the tree to v
31    long INF = Long.MAX_VALUE / 2;
32    long[] key = new long[n];
33    Arrays.fill(key, INF);
34    key[s] = 0;
35    boolean[] in = new boolean[n];
36    long total = 0;
37    for (int step = 0; step < n; step++) {
38        int u = -1;
39        for (int v = 0; v < n; v++) if (!in[v] && key[v] < INF && (u == -1 || key[v] < key[u])) u = v;
40        if (u == -1) break;                             // the rest is unreachable
41        in[u] = true;
42        total += key[u];
43        for (int[] e : adj[u]) if (!in[e[0]] && e[1] < key[e[0]]) key[e[0]] = e[1];   // decrease key
44    }
45    return total;
46}

Live state

0 edges examined0 edges rejected

n

6

edges

8

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L3n=6 edges=8Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.
2L11edge=1-2:1 total=11-2:1 joins two different components: add it to the tree. Total weight 1.
3L11edge=1-3:2 total=31-3:2 joins two different components: add it to the tree. Total weight 3.
4L11edge=0-2:3 total=60-2:3 joins two different components: add it to the tree. Total weight 6.
5L9edge=0-1:40-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6L9edge=2-3:42-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7L11edge=2-4:5 total=112-4:5 joins two different components: add it to the tree. Total weight 11.
8L11edge=4-5:6 total=174-5:6 joins two different components: add it to the tree. Total weight 17.
9L9edge=3-4:73-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10L13return=17 components=1The tree has 5 edges and total weight 17 (the smallest possible).

Practice ladder

Now try it yourself

Easy

  • Find if Path Exists in Graph

Medium

  • Min Cost to Connect All Points
  • Connecting Cities With Minimum Cost
  • Number of Operations to Make Network Connected

Advanced

  • Optimize Water Distribution in a Village
  • Remove Max Number of Edges to Keep Graph Fully Traversable

Key takeaways

  • Kruskal: sort edges, take an edge when it joins two different components; O(m log m).
  • Union-find answers the connectivity test in nearly constant time.
  • After k accepted edges there are n - k trees; the total is the same for any tie-breaking.
  • On a disconnected graph Kruskal returns a minimum spanning forest.