A platform team has to light fiber between four DCs so every site can reach every other. They run Dijkstra from DC A. Each site gets a shortest path back to A. The bill is the sum of those spokes. Two DCs that sit 1 km apart each bought a long haul to headquarters. Nobody “chose a slow MST algorithm.” They solved shortest-path-from-A on a job that asked for a tree that spans, min total weight.
Prim grows that tree from a seed by always adding the cheapest edge that still crosses into the tree. The layout is an undirected weighted graph (Graphs). The frontier is a min-heap of those crossing edges (Heaps). Families and the catalog live on the Algorithms Roadmap. It is not a shortest-path procedure, not Kruskal’s sort-and-union walk, and not “any spanning tree will do.”
Same MST, pick by layout
An MST is a subset of edges that connects every vertex, has no cycle, and has the smallest possible total weight. That definition is the same job Kruskal solves. This post does not walk Kruskal’s sort-plus-union. The two names are two layouts of the same tree.
Dense graph, adjacency matrix already n² cells: grow from a seed. Sparse graph, you already hold an edge list: Kruskal is usually the cheaper scan. Pick by what the data looks like, not by which name you remember from an interview sheet.
Note: If the graph is disconnected, Prim spans the component that contains the seed. A full forest needs a new seed in each leftover component — or Kruskal on the whole edge list. Connected input is the walk below.
Negative weights are legal. MST is total weight of a tree, not a distance from s. Dijkstra’s non-negative rule is a different job; do not import it here.
Grow the tree from a seed
Start with one vertex s in the tree. The heap holds crossing edges: one end in the tree, the other not. Repeatedly:
- Pop the cheapest crossing edge
(weight, to, from). - Skip it if
tois already in the tree (a stale, more expensive way in — lazy, not decrease-key). - Add
toand the edgefrom — toto the MST. - Push every edge out of
towhose other end is still outside the tree.
Stop when every vertex is in the tree, or the heap is empty (the leftover vertices are another component). You never scan every spanning tree. You grow one from the seed.
The other packaging keys vertices by cheapest edge into the tree (distToTree[v]), and lazy-repush when a cheaper crossing shows up. Same MST. Same heap. Different tuple. This post’s sketch uses crossing edges; one sentence of the vertex-keyed cousin is enough.
Dijkstra from the seed is not an MST. Dijkstra would keep distances from A. Prim keeps the cheapest edge into the tree. Those two numbers agree only by accident.
Note: Undirected means both directions already sit in the neighbor lists, same weight. A one-way adjacency list is a directed graph, and MST is not defined there.
A walked pass from seed A
Four DCs. The expensive spoke A — C is the Dijkstra trap: it is the shortest path from A to C, and it does not belong in the MST.
undirected, weighted:
A --6-- C
|5 |1
B --5-- D
A --10- D
seed A
inMst: {A}
pq: (5, B, A), (6, C, A), (10, D, A)
pop (5,B,A) add B tree edge A—B (5)
push B→D (5, D, B)
pq: (5, D, B), (6, C, A), (10, D, A)
pop (5,D,B) add D tree edge B—D (5)
push D→C (1, C, D)
pq: (1, C, D), (6, C, A), (10, D, A)
pop (1,C,D) add C tree edge D—C (1)
C's other ends already in the tree
pq: (6, C, A), (10, D, A)
pop (6,C,A) C already inMst skip
pop (10,D,A) D already inMst skip
MST: A—B (5), B—D (5), D—C (1) total 11
not: A—C (6) — shortest A ⇝ C, wrong treeEach honest pop adds one vertex. The leftover (6, C, A) and (10, D, A) are ghosts from when C and D were still outside. Skipping them is the whole lazy story. Empty graph and a seed with no edges: the tree is {A}, heap drains, everyone else stays unreachable from that seed.
Dijkstra from A would settle dist[C] = 6 on the spoke and never look at D — C. Prim does the opposite: once D is in, the 1-weight crossing beats the spoke.
Dijkstra-shaped frontier, MST job
The heap is the tool the Heaps post already taught. Dijkstra already used that frontier to settle distances from a source. This post does not re-teach the heap, decrease-key, or Dijkstra’s shortest-path invariant.
The resemblance is the pop-skip-push loop. The job is different: the key on the heap is “cheapest edge into the tree,” not “distance from A.” First honest add of v is the MST parent of v for this seed. Later pairs for v are stale; drop them.
A Fibonacci heap is a name in a decrease-key bound. The heaps post already said not to build one. This sketch will not either.
Note: You may also keep distToTree and ignore a pop whose weight is worse than the best crossing you have already recorded. Same lazy-repush rule, vertex-keyed. Do not reopen a vertex that is already in the MST “just in case.”
Java sketch
Weighted list as in the graph post: Edge(to, weight), both directions stored. The heap is a min-heap of crossing triples. Stale pops are the continue.
record Edge(String to, int weight) {}
record Crossing(int weight, String to, String from) {}
static List<Crossing> prim(
Map<String, List<Edge>> g, String seed) {
Set<String> inMst = new HashSet<>();
List<Crossing> mst = new ArrayList<>();
PriorityQueue<Crossing> pq = new PriorityQueue<>(
Comparator.comparingInt(Crossing::weight));
inMst.add(seed);
for (Edge e : g.getOrDefault(seed, List.of())) {
pq.add(new Crossing(e.weight(), e.to(), seed));
}
while (!pq.isEmpty() && inMst.size() < g.size()) {
Crossing cur = pq.poll();
if (inMst.contains(cur.to())) {
continue; // already in the tree; cheaper edge won
}
inMst.add(cur.to());
mst.add(cur);
for (Edge e : g.getOrDefault(cur.to(), List.of())) {
if (!inMst.contains(e.to())) {
pq.add(new Crossing(e.weight(), e.to(), cur.to()));
}
}
}
return mst;
}Vertex-keyed cousin: keep distToTree (cheapest known crossing into v), push (distToTree[v], v) when it improves, skip a pop that does not match. Same lazy re-push. Same MST. This sketch owns the edge triples.
Vertices that appear only as Edge.to need a putIfAbsent when you add edges, same as the graph post’s addVertex. The sketch assumes the map already has every vertex key, and that you inserted u → v and v → u for each undirected edge.
Note: If inMst.size() never reaches g.size(), the leftover vertices were in another component. The list is a spanning tree of the seed’s component, not a silent success for the whole vertex set.
Complexity
Let V be vertices, E edges. Binary heap, lazy re-push, each undirected edge considered from a newly added vertex.
| Time (heap) | O(E log E) heap ops, usually written O(E log V) |
| Time (dense matrix) | O(V²): scan the cheapest vertex not yet in the tree; no heap |
| Extra RAM | inMst, MST edge list, heap of up to O(E) triples |
First add of v | Cheapest edge from the current tree into v |
| Fibonacci heap | Name only: do not implement |
Glossary and the Big-O reading live on the hub. The bill that kills the fiber plan is the wrong job (distances from A), not a missing Fibonacci heap.
On a dense n × n matrix you already paid Θ(V²) to store the graph. The matrix Prim that scans distToTree each round matches that bill. On a sparse edge list, Kruskal is usually the scan you wanted.
When not to run Prim
Skip it when:
- The graph is directed. MST is an undirected object. One-way links are a different tree (arborescence) — not this post.
- You needed shortest path from
s. That is Dijkstra when weights are non-negative. An MST parent ofvis not a shortests ⇝ v. - Weights do not matter. “Just connect them” is any spanning tree: DFS or BFS from a seed, no heap. Prim is cargo-cult of the name.
- The layout is a sparse edge list. Kruskal on that list is the usual pick. Do not build an
n × nmatrix so you can run Prim. - A library already spans. Network design solvers and graph DBs already grow spanning trees. Pasting this sketch into a request path is the wrong system boundary.
Do not run Prim to get distances from a source when Dijkstra already answers. Do not run it on a directed service graph and call the parent map an MST.
Also skip it when there is no seed because you wanted “cheapest edges that do not cycle” on an edge list — that is Kruskal, named once, not re-walked here.
JDK: a PriorityQueue, not a Prim class
There is no java.util.Prim. The library piece is the frontier:
- Heap:
PriorityQueuewithComparator.comparingInt(Crossing::weight) - Layout:
Map<K, List<Edge>>as in the graph post, both directions stored - Membership: an
inMstset you test on every pop
Prefer Prim when the graph is dense or already a matrix. Reach for Kruskal when you already hold a sparse edge list. Reach for Dijkstra when the question is distance from a source, not total tree weight.
Do not remove from the heap to fake decrease-key. Do not sort the whole edge list inside this procedure. Do not implement a Fibonacci heap.
Cheat sheet
Job: MST from a seed; tree that spans, min total weight
Frontier: min-heap of crossing (weight, to, from) — PriorityQueue
Add: cheapest edge into a vertex still outside the tree
Skip: pop whose to is already inMst (lazy; not decrease-key)
Dijkstra: same-shaped heap; distances from s, not MST
Kruskal: same MST; sparse edge list + union; do not walk it here
Dense: adjacency matrix / O(V²) scan is Prim's home turf
Unweighted: any spanning tree (DFS/BFS); no heap
Directed: not this algorithm (MST is undirected)
JDK: PriorityQueue; no Prim type; no Fibonacci heap
Do not: Dijkstra on a wiring job; Prim on a directed graphDo:
- Grow from a seed with a heap of crossing edges.
- Skip stale pops. That is the JDK-shaped algorithm.
- Pick Prim vs Kruskal by layout (dense matrix vs sparse edge list).
Don’t:
- Treat shortest paths from A as an MST when the bill is total tree weight.
- Re-teach or re-implement the heap; link it, use
PriorityQueue. - Run this procedure on directed edges, or on “just connect them.”
- Reach for a Fibonacci heap because a complexity table named one.
Wrap-up
Prim is a Dijkstra-shaped min-heap used for an MST: start at a seed, always add the cheapest edge that still crosses into the tree, lazy-skip when to is already inside. The first honest add of a vertex is its MST parent for that seed. Dijkstra would have kept distances from A; Prim keeps cheapest-into-the-tree. Same MST as Kruskal — pick Prim on a dense matrix, Kruskal on a sparse edge list. The JDK gives you PriorityQueue, not a turnkey spanning-tree class. Use any spanning tree when weights do not matter. Hand-roll the sketch when the undirected weights and the seed are the assignment.
The next procedure in this wave leaves spanning trees: collapse a directed graph to a DAG of strongly connected components.