DSA Tracker

Visualize

Min Cost to Connect All Points

Priority queue with lazy deletion: pop the cheapest edge, skip it if it's stale

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

Push (0, vertex 0) onto a min-priority-queue keyed by edge weight, then repeatedly pop the cheapest entry. If it names a vertex already in the tree, it's a stale leftover from before a cheaper route was found — discard it and move on. Otherwise the popped vertex is genuinely the cheapest way in right now, so absorb it, add its edge weight to the running total, and push every edge to its still-unvisited neighbours. The queue can hold several entries for the same vertex at once; only the cheapest one that survives to be popped ever does real work.

Details

Animated on: n = 5 vertices, edges [[0,1,2],[0,3,6],[1,2,3],[1,3,8],[1,4,5],[2,4,7],[3,4,9]] — find the minimum spanning tree's total weight using Prim's algorithm.

Problem:Min Cost to Connect All PointsMedium

Pattern:Minimum Spanning Tree and Graph Greedy

Priority queue with lazy deletion: pop the cheapest edge, skip it if it's stale

step 1 / 14

Weighted graph — build the minimum spanning tree from vertex 0

5 vertices, 7 weighted edges. Push (0, vertex 0) onto a priority queue and always pop the cheapest entry next — if it names a vertex already in the tree, it is a stale leftover from an earlier, more expensive push, so it is simply discarded.

Pseudocode
1FUNCTION primMST(n, edges):
2  BUILD adjacency list from edges
3  pq <- MIN-HEAP with (0, 0, -1)
4  visited[0..n-1] <- FALSE
5  total <- 0
6  WHILE pq NOT EMPTY
7    (w, u, parent) <- EXTRACT-MIN(pq)
8    IF visited[u]: CONTINUE
9    visited[u] <- TRUE
10    total <- total + w
11    FOR EACH (v, weight) IN ADJACENT(u)
12      IF NOT visited[v]
13        PUSH (weight, v, u) TO pq
14  RETURN total

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. 5 vertices, 7 weighted edges. Push (0, vertex 0) onto a priority queue and always pop the cheapest entry next — if it names a vertex already in the tree, it is a stale leftover from an earlier, more expensive push, so it is simply discarded.
  2. Pop (0, 0) — vertex 0 seeds the tree for free.
  3. Push (2, 1), (6, 3) onto the queue for 0's unvisited neighbours.
  4. Pop (2, 1) — the cheapest live entry left in the queue. Vertex 1 joins the tree via edge 0-1.
  5. Add edge 0-1 (weight 2) — running total is now 2. Push (3, 2), (8, 3), (5, 4) onto the queue for 1's unvisited neighbours.
  6. Pop (3, 2) — the cheapest live entry left in the queue. Vertex 2 joins the tree via edge 1-2.
  7. Add edge 1-2 (weight 3) — running total is now 5. Push (7, 4) onto the queue for 2's unvisited neighbours.
  8. Pop (5, 4) — the cheapest live entry left in the queue. Vertex 4 joins the tree via edge 1-4.
  9. Add edge 1-4 (weight 5) — running total is now 10. Push (9, 3) onto the queue for 4's unvisited neighbours.
  10. Pop (6, 3) — the cheapest live entry left in the queue. Vertex 3 joins the tree via edge 0-3.
  11. Add edge 0-3 (weight 6) — running total is now 16. 3 has no unvisited neighbours left to push.
  12. Pop (7, 4) — vertex 4 is already in the tree via a cheaper edge, so this stale queue entry is discarded with no work done.
  13. Pop (8, 3) — vertex 3 is already in the tree via a cheaper edge, so this stale queue entry is discarded with no work done.
  14. Pop (9, 3) — vertex 3 is already in the tree via a cheaper edge, so this stale queue entry is discarded with no work done.

Now solve it yourself

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

Solve Min Cost to Connect All Points in the editorAll Graph problemsBack to roadmap