Prim's Algorithm is a greedy algorithm for constructing a Minimum Spanning Tree (MST) of a weighted, undirected, connected graph.

Its objective is not shortest paths from a source. Instead, it minimizes the total weight of the edges used to connect all vertices.

Minimum Spanning Tree

A spanning tree:

• includes every vertex,
• is connected,
• contains no cycle,
• has exactly V-1 edges.

An MST is the spanning tree with minimum total edge weight.

Core idea

Prim grows one tree.

At every step:

1. keep a set of vertices already inside the tree,
2. consider edges crossing from visited to unvisited vertices,
3. choose the minimum-weight crossing edge,
4. add the new vertex,
5. repeat until all vertices are included.

Why the greedy choice works

Prim relies on the Cut Property:

For any cut of the graph, a lightest edge crossing that cut belongs to some MST.

At each step, the visited/unvisited partition forms exactly such a cut.

JavaScript with a priority queue concept

function prim(graph, start) {
  const visited = new Set();
  const mst = [];
  const candidates = [
    [0, null, start]
  ];

  let totalWeight = 0;

  while (candidates.length > 0) {
    candidates.sort(
      (a, b) => a[0] - b[0]
    );

    const [
      weight,
      from,
      node
    ] = candidates.shift();

    if (visited.has(node)) {
      continue;
    }

    visited.add(node);

    if (from !== null) {
      mst.push([
        from,
        node,
        weight
      ]);

      totalWeight += weight;
    }

    for (
      const [next, cost]
      of graph[node] ?? []
    ) {
      if (!visited.has(next)) {
        candidates.push([
          cost,
          node,
          next
        ]);
      }
    }
  }

  return {
    mst,
    totalWeight
  };
}

For production use, replace repeated sorting with a real min-heap.

Prim vs Kruskal

Both build MSTs.

Prim:

grows one connected tree

Kruskal:

sorts edges globally
+ uses Union-Find

Prim is often natural with adjacency lists or matrices.

Kruskal is especially convenient when the graph is already represented as an edge list.

Prim vs Dijkstra

This distinction is crucial.

Prim minimizes:

total weight of the spanning tree

Dijkstra minimizes:

distance from one source to every vertex

They can both use a priority queue, but their greedy keys and objectives are different.

Negative edge weights

Negative edges are allowed in MST problems.

Unlike shortest-path problems, a negative cycle does not create an unbounded optimum because an MST never contains a cycle.

Disconnected graphs

A single MST for the entire graph exists only if the graph is connected.

For disconnected graphs, run Prim independently on each component to obtain a Minimum Spanning Forest.

Dense vs sparse graphs

With an adjacency matrix and linear minimum-key selection:

O(V²)

can be attractive for dense graphs.

With adjacency lists and a binary heap:

O(E log V)

is standard.

Edge-based vs key-based Prim

Two common implementations exist.

Edge-based Prim stores candidate edges:

(weight, from, to)

Key-based Prim stores, for each unvisited vertex, the cheapest known connection into the current tree.

Both implement the same greedy principle.

Multiple MSTs

If all edge weights are distinct, the MST is unique.

With equal weights, several different MSTs may have the same minimum total cost.

Tie-breaking can therefore affect the exact edge set.

Real-world applications

Prim can model cost-minimal connection backbones such as:

• fiber layouts,
• cable networks,
• basic data-center interconnects,
• utility connections,
• sensor networks,
• road or pipeline design abstractions.

However, a pure MST minimizes cost, not redundancy.

Reliability caveat

An MST is a tree, so it contains no alternate route.

Every selected edge is a bridge in that tree.

Real production networks often add extra links after an MST-style cost baseline to improve fault tolerance.

MST and clustering

MSTs also appear in clustering.

A common idea is to build an MST and remove one or more of its largest edges to split the data into groups.

Directed graphs

Classic Prim applies to weighted undirected graphs.

Directed minimum-spanning structures require different algorithms such as Chu-Liu/Edmonds for arborescences.

Edge cases

• empty graph,
• one vertex,
• disconnected graph,
• duplicate edges,
• self-loops,
• negative weights,
• equal weights,
• invalid start vertex.

TypeScript

type NodeId = string;

type Neighbor = [
  node: NodeId,
  weight: number
];

type Graph =
  Record<NodeId, Neighbor[]>;

type MSTEdge = [
  from: NodeId,
  to: NodeId,
  weight: number
];

type PrimResult = {
  edges: MSTEdge[];
  totalWeight: number;
  connected: boolean;
};

function prim(
  graph: Graph,
  start: NodeId
): PrimResult {
  const nodes = new Set<NodeId>();

  for (
    const [u, neighbors]
    of Object.entries(graph)
  ) {
    nodes.add(u);

    for (const [v] of neighbors) {
      nodes.add(v);
    }
  }

  if (!nodes.has(start)) {
    return {
      edges: [],
      totalWeight: 0,
      connected: false
    };
  }

  const visited = new Set<NodeId>();
  const candidates:
    Array<[number, NodeId | null, NodeId]> = [
      [0, null, start]
    ];

  const edges: MSTEdge[] = [];
  let totalWeight = 0;

  while (candidates.length > 0) {
    candidates.sort(
      (a, b) => a[0] - b[0]
    );

    const [
      weight,
      from,
      node
    ] = candidates.shift()!;

    if (visited.has(node)) {
      continue;
    }

    visited.add(node);

    if (from !== null) {
      edges.push([
        from,
        node,
        weight
      ]);

      totalWeight += weight;
    }

    for (
      const [next, cost]
      of graph[node] ?? []
    ) {
      if (!visited.has(next)) {
        candidates.push([
          cost,
          node,
          next
        ]);
      }
    }
  }

  return {
    edges,
    totalWeight,
    connected:
      visited.size === nodes.size
  };
}

Complexity

With adjacency list + binary heap:

O(E log V)

A simple edge-heap implementation may also be described as:

O(E log E)

With an adjacency matrix:

O(V²)

Common mistakes

• confusing Prim with Dijkstra,
• applying classic Prim to directed graphs,
• forgetting disconnected graphs,
• using repeated array sorting instead of a heap at scale,
• forgetting to represent undirected edges in both adjacency directions,
• assuming MST means high reliability.

Summary

Prim's algorithm solves:

connect every vertex
with minimum total edge cost
without cycles

It is one of the two standard MST algorithms, alongside Kruskal.

Use it when the problem is a weighted undirected connectivity problem rather than a shortest-path problem.