Algorithms/Graph/Prim's MST

Prim's MST

Grow a minimum spanning tree one vertex at a time using a min-priority queue — O(E log V).

GraphMSTGreedyPriority QueueO(E log V)

Graph Visualization

Root

MST: 0Cost: 0Tree: 0PQ: 0

1 / 0

Speed

prims.js

1function prim(graph, start) {

2 const inTree = new Set([start]);

3 const keys = {}; // min edge weight into tree

4 const parent = {}; // tree-side endpoint

5 const pq = new MinHeap();

7 // Seed the frontier with start's neighbours

8 for (const e of graph.edgesFrom(start)) {

9 pq.push(e.to, e.weight);

10 keys[e.to] = e.weight;

11 parent[e.to] = start;

12 }

14 while (!pq.isEmpty()) {

15 const { node, edge } = pq.pop();

16 if (inTree.has(node)) continue;

18 // Take the cheapest frontier edge

19 mst.push(edge);

20 inTree.add(node);

22 // Update keys for the new node's neighbours

23 for (const e of graph.edgesFrom(node)) {

24 if (inTree.has(e.to)) continue;

25 if (e.weight < keys[e.to]) {

26 keys[e.to] = e.weight;

27 parent[e.to] = node;

28 pq.push(e.to, e.weight);

29 }

30 }

31 }

33 return mst;

34}

Algorithm Explanation

Prim's algorithm builds a Minimum Spanning Tree (MST) by starting at a chosen root node and repeatedly attaching the cheapest edge that connects the growing tree to a vertex outside it.

⚙️ How It Works

Pick a root — every MST produced by Prim's depends on the starting vertex, but the total cost is always the same.
Seed the frontier. Push every edge incident to the root into a min-priority queue keyed on weight. Each frontier vertex also gets a "key" (the cheapest known edge into the tree) and a parent pointer back to the in-tree endpoint.
Pop the cheapest edge. If its outer endpoint is already in the tree, discard (stale PQ entry). Otherwise, add the edge and the vertex to the MST.
Decrease-key neighbours: for each neighbour of the newly added vertex, if the new edge is cheaper than its current key, update the key and push the new candidate into the PQ.
Stop after V-1 edges have been accepted — the MST is complete.

🧩 Why a Priority Queue?

The naive "scan every frontier edge on every step" approach is O(V²). Using a binary min-heap or a Fibonacci heap for the priority queue reduces the total cost to O(E log V), making Prim's practical on large dense graphs.

💡 Cut property: For any cut of the graph (a partition of nodes into two non-empty sets), the minimum-weight edge crossing that cut belongs to some MST. Prim's repeatedly exploits this cut property by treating the growing tree as one side of the cut and the frontier as the other.

⚖️ Prim's vs Kruskal's

Prim's (this page)

Grows one connected component from a seed — O(E log V).
Uses a priority queue keyed on minimum edge leaving the tree.
Node-centric — better on dense graphs.
Requires connectivity (or a super-source) to span the graph.

Kruskal's

Sorts all edges up front — O(E log E).
Uses Union-Find for cycle detection.
Edge-centric — natural for sparse graphs.
Produces a Minimum Spanning Forest if the graph is disconnected.

Pick a root (or click a node) · Watch the tree grow via the cheapest reachable edge · Frontier edges show the priority queue