36.03Intermediate / Advanced4 topics15 min4 interactive animations

Prim's algorithm

Prim's algorithm grows one tree from a start vertex, always adding the cheapest edge that leaves the tree; with a heap it runs in O((n + m) log n), and a plain array gives O(n²) for dense graphs.

Learning goals

Run Prim with a heap of frontier edges
Compare the lazy version with the eager version that keeps one key per vertex
Build the adjacency list from an edge list
Use the array version on dense graphs

Prerequisites

MST definitionsPriority queuesDijkstra's algorithm

Prim looks like Dijkstra, but a vertex's priority is the weight of one edge to the tree, not the length of a whole path. Which algorithm is better depends on the graph: sparse favours Kruskal or heap Prim, dense favours array Prim.

36.03.1

Frontier heap

Start with one vertex. The **frontier** is the set of edges with exactly one end in the tree. Take the lightest frontier edge (the cut property again, with S = the tree), add its far vertex, and put that vertex's edges on the frontier. A min-heap holds the frontier.

In the **lazy** version an edge stays in the heap after its far end joined the tree some other way; when it is popped it is discarded as outdated. The heap can hold up to m entries and the cost is O(m log m). Choose *Prim, lazy* in the animation: outdated entries are drawn struck out.

Java

1static long primLazy(int n, List<int[]>[] adj, int s) {            // adj[u] = {v, w}; weight of the tree of s's component
2    boolean[] in = new boolean[n];
3    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));   // {vertex, weight of the edge that reaches it}
4    pq.add(new int[]{s, 0});
5    long total = 0;
6    while (!pq.isEmpty()) {
7        int[] top = pq.poll();
8        if (in[top[0]]) continue;                                   // outdated entry: already in the tree
9        in[top[0]] = true;
10        total += top[1];
11        for (int[] e : adj[top[0]]) if (!in[e[0]]) pq.add(new int[]{e[0], e[1]});
12    }
13    return total;
14}

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

Interactive · edit the input

undirected graph · 6 vertices · 8 edges

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

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

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3	n=6 edges=8	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.
2	L11	edge=1-2:1 total=1	1-2:1 joins two different components: add it to the tree. Total weight 1.
3	L11	edge=1-3:2 total=3	1-3:2 joins two different components: add it to the tree. Total weight 3.
4	L11	edge=0-2:3 total=6	0-2:3 joins two different components: add it to the tree. Total weight 6.
5	L9	edge=0-1:4	0-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6	L9	edge=2-3:4	2-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7	L11	edge=2-4:5 total=11	2-4:5 joins two different components: add it to the tree. Total weight 11.
8	L11	edge=4-5:6 total=17	4-5:6 joins two different components: add it to the tree. Total weight 17.
9	L9	edge=3-4:7	3-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10	L13	return=17 components=1	The tree has 5 edges and total weight 17 (the smallest possible).

36.03.2

Eager/lazy versions

The **eager** version keeps for each outside vertex only the cheapest edge found so far, key[v]. When a new vertex joins the tree, its edges can lower the keys of neighbours; the heap entry is replaced (decrease-key). The heap then holds at most n entries and the cost is O(m log n).

Java's PriorityQueue cannot decrease a key cheaply, so the code uses a TreeSet ordered by {key, vertex} as an indexed heap: remove the old entry and insert the new one, both O(log n). The *Prim, eager* animation shows the key row.

Java

1static long primEagerTree(int n, List<int[]>[] adj, int s) {         // one entry per vertex
2    long INF = Long.MAX_VALUE / 2;
3    long[] key = new long[n];
4    Arrays.fill(key, INF);
5    key[s] = 0;
6    boolean[] in = new boolean[n];
7    TreeSet<long[]> open = new TreeSet<>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));   // {key, vertex}
8    open.add(new long[]{0, s});
9    long total = 0;
10    while (!open.isEmpty()) {
11        long[] top = open.pollFirst();
12        int u = (int) top[1];
13        in[u] = true;
14        total += top[0];
15        for (int[] e : adj[u]) {
16            if (in[e[0]] || e[1] >= key[e[0]]) continue;
17            if (key[e[0]] != INF) open.remove(new long[]{key[e[0]], e[0]});   // decrease key: replace the entry
18            key[e[0]] = e[1];
19            open.add(new long[]{e[1], e[0]});
20        }
21    }
22    return total;
23}

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

Interactive · edit the input

undirected graph · 6 vertices · 8 edges

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

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

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3	n=6 edges=8	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.
2	L11	edge=1-2:1 total=1	1-2:1 joins two different components: add it to the tree. Total weight 1.
3	L11	edge=1-3:2 total=3	1-3:2 joins two different components: add it to the tree. Total weight 3.
4	L11	edge=0-2:3 total=6	0-2:3 joins two different components: add it to the tree. Total weight 6.
5	L9	edge=0-1:4	0-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6	L9	edge=2-3:4	2-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7	L11	edge=2-4:5 total=11	2-4:5 joins two different components: add it to the tree. Total weight 11.
8	L11	edge=4-5:6 total=17	4-5:6 joins two different components: add it to the tree. Total weight 17.
9	L9	edge=3-4:7	3-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10	L13	return=17 components=1	The tree has 5 edges and total weight 17 (the smallest possible).

36.03.3

Adjacency list

Prim needs the neighbours of the vertex it just added, so an **adjacency list** is the natural input: an array of lists, each entry {neighbour, weight}. An edge list is converted by adding each undirected edge to both endpoints' lists, in O(n + m).

Looking for the outgoing edges in an edge list would scan all m edges at every step and cost O(n · m). The same conversion step is the first line of almost every graph program.

Java

1static long primOnEdgeList(int n, int[][] edges) {                  // builds the lists first; weight of the tree containing vertex 0
2    List<int[]>[] adj = new List[n];
3    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
4    for (int[] e : edges) {
5        adj[e[0]].add(new int[]{e[1], e[2]});
6        adj[e[1]].add(new int[]{e[0], e[2]});
7    }
8    boolean[] in = new boolean[n];
9    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
10    pq.add(new int[]{0, 0});
11    long total = 0;
12    while (!pq.isEmpty()) {
13        int[] top = pq.poll();
14        if (in[top[0]]) continue;
15        in[top[0]] = true;
16        total += top[1];
17        for (int[] e : adj[top[0]]) if (!in[e[0]]) pq.add(e);
18    }
19    return total;
20}

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

Interactive · edit the input

undirected graph · 6 vertices · 8 edges

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

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

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3	n=6 edges=8	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.
2	L11	edge=1-2:1 total=1	1-2:1 joins two different components: add it to the tree. Total weight 1.
3	L11	edge=1-3:2 total=3	1-3:2 joins two different components: add it to the tree. Total weight 3.
4	L11	edge=0-2:3 total=6	0-2:3 joins two different components: add it to the tree. Total weight 6.
5	L9	edge=0-1:4	0-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6	L9	edge=2-3:4	2-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7	L11	edge=2-4:5 total=11	2-4:5 joins two different components: add it to the tree. Total weight 11.
8	L11	edge=4-5:6 total=17	4-5:6 joins two different components: add it to the tree. Total weight 17.
9	L9	edge=3-4:7	3-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10	L13	return=17 components=1	The tree has 5 edges and total weight 17 (the smallest possible).

36.03.4

Dense graph variant

When m is close to n², a heap is overkill. Keep key[v] in a plain array and find the smallest outside key by scanning all n entries each round: n rounds of O(n) is O(n²), with no sorting and no heap. The adjacency can be a matrix.

For a complete graph with n vertices, m is about n² / 2, so O(n²) beats Kruskal's O(m log m) and heap Prim's O(m log n). The array version is also the easiest to write correctly.

Java

1static long primDense(int[][] w) {                                   // w[i][j] = weight, Integer.MAX_VALUE when there is no edge
2    int n = w.length;
3    long[] key = new long[n];
4    Arrays.fill(key, Long.MAX_VALUE);
5    key[0] = 0;
6    boolean[] in = new boolean[n];
7    long total = 0;
8    for (int step = 0; step < n; step++) {
9        int u = -1;
10        for (int v = 0; v < n; v++) if (!in[v] && key[v] != Long.MAX_VALUE && (u == -1 || key[v] < key[u])) u = v;
11        if (u == -1) break;                                          // the rest is unreachable
12        in[u] = true;
13        total += key[u];
14        for (int v = 0; v < n; v++)
15            if (!in[v] && w[u][v] != Integer.MAX_VALUE && w[u][v] < key[v]) key[v] = w[u][v];
16    }
17    return total;
18}

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

Interactive · edit the input

undirected graph · 6 vertices · 8 edges

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

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

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3	n=6 edges=8	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.
2	L11	edge=1-2:1 total=1	1-2:1 joins two different components: add it to the tree. Total weight 1.
3	L11	edge=1-3:2 total=3	1-3:2 joins two different components: add it to the tree. Total weight 3.
4	L11	edge=0-2:3 total=6	0-2:3 joins two different components: add it to the tree. Total weight 6.
5	L9	edge=0-1:4	0-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6	L9	edge=2-3:4	2-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7	L11	edge=2-4:5 total=11	2-4:5 joins two different components: add it to the tree. Total weight 11.
8	L11	edge=4-5:6 total=17	4-5:6 joins two different components: add it to the tree. Total weight 17.
9	L9	edge=3-4:7	3-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10	L13	return=17 components=1	The 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

Advanced

Optimize Water Distribution in a Village

Key takeaways

Prim grows one tree, always adding the lightest edge that leaves it.
Lazy Prim keeps outdated edges in the heap and skips them; eager Prim keeps one key per vertex with decrease-key.
Start from an adjacency list; an edge list makes every step scan all edges.
On dense graphs the array version runs in O(n²) without any heap.