jsschools

Prim's Algorithm

Builds a minimum spanning tree (MST) by greedily adding the cheapest edge that connects a visited vertex to an unvisited one, starting from any source node.

Spec ↗

Syntax

prim(graph, start)

Parameters

NameTypeRequiredDescription
graph Map<number, Array<{to: number, w: number}>> Yes Undirected weighted adjacency list. Edges should appear in both directions.
start number Yes Starting vertex. The MST is the same regardless of the starting node.

Returns

number — Total weight of the minimum spanning tree.

Examples

function prim(graph, start) {
  const inMST = new Set([start]);
  let totalWeight = 0;
  // collect all edges from start
  const edges = [...(graph.get(start) ?? [])].map(e => [e.w, start, e.to]);

  while (inMST.size < graph.size) {
    edges.sort((a, b) => a[0] - b[0]); // pick cheapest
    const idx = edges.findIndex(([, , to]) => !inMST.has(to));
    if (idx === -1) break; // disconnected
    const [w, , to] = edges.splice(idx, 1)[0];
    inMST.add(to);
    totalWeight += w;
    for (const e of graph.get(to) ?? []) {
      if (!inMST.has(e.to)) edges.push([e.w, to, e.to]);
    }
  }
  return totalWeight;
}

const g = new Map([
  [0, [{to:1,w:2},{to:3,w:6}]],
  [1, [{to:0,w:2},{to:2,w:3},{to:3,w:8},{to:4,w:5}]],
  [2, [{to:1,w:3},{to:4,w:7}]],
  [3, [{to:0,w:6},{to:1,w:8},{to:4,w:9}]],
  [4, [{to:1,w:5},{to:2,w:7},{to:3,w:9}]],
]);
console.log(prim(g, 0));
Output 
16

// MST edges (track parent)
function primEdges(graph, start) {
  const inMST = new Set([start]);
  const mstEdges = [];
  const edges = [...(graph.get(start)??[])].map(e=>[e.w,start,e.to]);
  while (inMST.size < graph.size) {
    edges.sort((a,b)=>a[0]-b[0]);
    const idx = edges.findIndex(([,,to])=>!inMST.has(to));
    if (idx===-1) break;
    const [w,u,to] = edges.splice(idx,1)[0];
    inMST.add(to);
    mstEdges.push({u,v:to,w});
    for (const e of graph.get(to)??[])
      if (!inMST.has(e.to)) edges.push([e.w,to,e.to]);
  }
  return mstEdges;
}

const g = new Map([[0,[{to:1,w:1},{to:2,w:4}]],[1,[{to:0,w:1},{to:2,w:2}]],[2,[{to:1,w:2},{to:0,w:4}]]]);
console.log(primEdges(g,0).map(e=>`${e.u}-${e.v}:${e.w}`).join(', '));
Output 
0-1:1, 1-2:2

Notes

| Case | Time | Space | |---------|---------------------|-------| | Best | O((V + E) log V) | O(V) | | Average | O((V + E) log V) | O(V) | | Worst | O((V + E) log V) | O(V) | With a proper min-heap. The naive array-based implementation above is O(V²). Prim's works only on **connected undirected** graphs. For dense graphs (E ≈ V²) the O(V²) version is competitive with the heap version. Kruskal's algorithm is an alternative MST algorithm that works better for sparse graphs and is simpler to implement with a Union-Find structure.

See also