Prim's MST
Grow a minimum spanning tree by greedily adding the cheapest edge to the frontier.
How it works
Prim's algorithm constructs a Minimum Spanning Tree (MST) — a subset of edges that connects all vertices with the minimum total weight and no cycles. It works greedily: starting from any node, it repeatedly picks the cheapest edge that crosses the cut between nodes already in the MST and those not yet included. This greedy choice is provably optimal by the cut property of matroids: the minimum-weight crossing edge of any cut is always safe to add to an MST.
The algorithm maintains a key array where key[v] is the minimum edge weight needed to connect v to the current MST. When a node u is added to the MST, all its neighbors v are checked — if the edge u–v is cheaper than the current key[v], the key is updated. This is structurally similar to Dijkstra's algorithm, but the priority is the edge weight directly rather than the cumulative path distance from the source.
Prim's algorithm is particularly efficient on dense graphs — with a Fibonacci heap it achieves O(E + V log V), which is faster than Kruskal's O(E log E) when E >> V. However, for sparse graphs both are comparable. The MST produced by Prim is unique when all edge weights are distinct, and represents the globally cheapest way to connect all nodes in the network.
Complexity
Visualizer
Where it's used in the real world
Network infrastructure planning
Laying minimum-cost fiber cable to connect all buildingsA campus or city network must physically connect every building (node) with fiber (edges). The MST gives the cheapest wiring plan — no unnecessary loops, every building reachable. Prim's algorithm is run on the graph of possible cable routes weighted by installation cost.
Cluster computing — job scheduling
Connecting compute nodes with minimum inter-node bandwidth costHigh-performance clusters model inter-node communication cost as a weighted graph. An MST identifies the spanning topology with minimum total bandwidth overhead, used when configuring collective communication trees (e.g. MPI_Bcast) to reduce latency and network congestion.
VLSI circuit design
Minimizing wire length when routing connections between chip componentsRouting wires between components on a chip is modeled as a Steiner tree or MST problem on the layout grid. Prim's algorithm (or variants) finds connections with minimum total wire length, directly reducing signal propagation delay and power consumption — critical in modern processor design.
Implementation
function primMST(
nodes: string[],
edges: { from: string; to: string; weight: number }[]
): { totalWeight: number; mstEdges: [string, string, number][] } {
const INF = Infinity;
const key: Record<string, number> = Object.fromEntries(nodes.map(n => [n, INF]));
const parent: Record<string, string | null> = Object.fromEntries(nodes.map(n => [n, null]));
const inMST = new Set<string>();
// Undirected adjacency list
const adj = new Map<string, Array<{ to: string; w: number }>>();
for (const n of nodes) adj.set(n, []);
for (const { from, to, weight } of edges) {
adj.get(from)!.push({ to, w: weight });
adj.get(to)!.push({ to: from, w: weight });
}
key[nodes[0]] = 0;
const mstEdges: [string, string, number][] = [];
for (let i = 0; i < nodes.length; i++) {
// Pick min-key node not in MST (O(V) scan; use a heap for O(log V))
let u: string | null = null;
let minKey = INF;
for (const n of nodes) {
if (!inMST.has(n) && key[n] < minKey) { minKey = key[n]; u = n; }
}
if (u === null) break;
inMST.add(u);
if (parent[u] !== null) {
mstEdges.push([parent[u]!, u, key[u]]);
}
for (const { to: v, w } of adj.get(u)!) {
if (!inMST.has(v) && w < key[v]) {
key[v] = w;
parent[v] = u;
}
}
}
const totalWeight = mstEdges.reduce((s, [,, w]) => s + w, 0);
return { totalWeight, mstEdges };
}