Prim's MST

Graphs

avgO(V²)worstO(V²)spaceO(V)

Grow the tree from A: its key is 0 and every other key is ∞

1 / 38

Code

function prim(graph: Graph, source: number) {  const key = new Array(graph.size).fill(Infinity);  const parent = new Array<number | null>(graph.size).fill(null);  const inTree = new Set<number>();  const mst: [number, number][] = [];  key[source] = 0;  while (inTree.size < graph.size) {    // The cheapest known edge into the tree picks the next node.    const u = argMin(key, (v) => !inTree.has(v));    if (key[u] === Infinity) break; // disconnected: the rest can't be reached    inTree.add(u);    if (parent[u] !== null) mst.push([parent[u], u]);    for (const { to, weight } of graph.edgesFrom(u)) {      if (inTree.has(to) || weight >= key[to]) continue;      key[to] = weight;      parent[to] = u;    }  }  return mst;}

procedure Prim(G, source)  key[v] ← ∞ for every node v    ▷ cheapest edge seen into v  parent[v] ← none for every node v  inTree ← ∅  mst ← []  key[source] ← 0  while some node is not in the tree do    ▷ grow the tree by its cheapest outgoing edge    u ← the node ∉ inTree with the smallest key    if key[u] = ∞ then stop    ▷ G is disconnected    add u to inTree    if parent[u] exists then add edge (parent[u], u) to mst    for each edge (u, to, weight) do      if to ∈ inTree or weight ≥ key[to] then skip it      key[to] ← weight      parent[to] ← u    end for  end while  return mstend procedure

Variables

none

Counters

edges considered: 0
key updates: 0

Nodes8

Source

Edgesweights 1 to 99

How it works

Prim's algorithm grows a minimum spanning tree from a single node, each round adding the cheapest edge that connects the tree to a node outside it. Every node keeps the weight of its cheapest known link to the tree (its key), so picking the next edge means picking the smallest key. This version scans the keys, the O(V²) form that suits small dense graphs.

Complexity

Best: O(V²)
Average: O(V²)
Worst: O(V²)
Space: O(V)

Prim's MST

How it works

Complexity

Search algorithms