Pattern visualizer

Minimum Spanning Tree (Prim)

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. 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..

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

time O(E log V)space O(V + E)step 1 / 14

Weighted graph — build the minimum spanning tree from vertex 0

line 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.

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap