Minimum Spanning Tree Prim's Algorithm in DSA Typescript

Mental Model

Start from any node and keep adding the cheapest edge that connects a new node to the growing tree until all nodes are included.

Analogy: Imagine building roads to connect all cities with the least total cost by always choosing the shortest new road from the cities already connected.

Graph:
  (A)
 /   \
5     3
/       \
(B)---4---(C)

Start at A, pick edges with smallest cost to connect all nodes.

Dry Run Walkthrough

Input: Graph with nodes A, B, C and edges: A-B=5, A-C=3, B-C=4; start from node A

Goal: Build a tree connecting all nodes with minimum total edge cost

Step 1: Start from node A, add it to MST set

MST nodes: [A]
Edges considered: A-B(5), A-C(3)

Why: We need a starting point to begin building the MST

Step 2: Pick edge with smallest cost from A: A-C(3), add C to MST

MST nodes: [A, C]
Edges considered: A-B(5), C-B(4)

Why: Choose the cheapest edge connecting MST to a new node

Step 3: Pick smallest edge connecting MST to new node: C-B(4), add B to MST

MST nodes: [A, C, B]
All nodes connected

Why: Add remaining node with minimum cost edge

Result:

MST edges: A-C(3) -> C-B(4)
Total cost: 7

Annotated Code

DSA Typescript

class Graph {
  nodes: string[];
  edges: Map<string, Map<string, number>>;

  constructor(nodes: string[]) {
    this.nodes = nodes;
    this.edges = new Map();
    for (const node of nodes) {
      this.edges.set(node, new Map());
    }
  }

  addEdge(u: string, v: string, weight: number) {
    this.edges.get(u)?.set(v, weight);
    this.edges.get(v)?.set(u, weight);
  }
}

function primMST(graph: Graph, start: string): [string, string, number][] {
  const mstEdges: [string, string, number][] = [];
  const visited = new Set<string>();
  const minHeap: {node: string; from: string | null; weight: number}[] = [];

  // Add start node edges to heap
  visited.add(start);
  for (const [neighbor, weight] of graph.edges.get(start)!) {
    minHeap.push({node: neighbor, from: start, weight});
  }

  // Helper to get smallest edge
  function extractMin() {
    let minIndex = 0;
    for (let i = 1; i < minHeap.length; i++) {
      if (minHeap[i].weight < minHeap[minIndex].weight) {
        minIndex = i;
      }
    }
    return minHeap.splice(minIndex, 1)[0];
  }

  while (minHeap.length > 0 && visited.size < graph.nodes.length) {
    const {node, from, weight} = extractMin();
    if (visited.has(node)) continue; // skip if already in MST
    visited.add(node);
    mstEdges.push([from!, node, weight]);

    // Add new edges from this node
    for (const [neighbor, w] of graph.edges.get(node)!) {
      if (!visited.has(neighbor)) {
        minHeap.push({node: neighbor, from: node, weight: w});
      }
    }
  }

  return mstEdges;
}

// Driver code
const graph = new Graph(['A', 'B', 'C']);
graph.addEdge('A', 'B', 5);
graph.addEdge('A', 'C', 3);
graph.addEdge('B', 'C', 4);

const mst = primMST(graph, 'A');
let totalCost = 0;
for (const [from, to, weight] of mst) {
  console.log(`${from} - ${to}: ${weight}`);
  totalCost += weight;
}
console.log(`Total cost: ${totalCost}`);

visited.add(start);

Mark start node as included in MST

for (const [neighbor, weight] of graph.edges.get(start)!) { minHeap.push({node: neighbor, from: start, weight}); }

Add all edges from start node to candidate edges

const {node, from, weight} = extractMin();

Select edge with smallest weight connecting MST to new node

if (visited.has(node)) continue;

Skip nodes already included to avoid cycles

visited.add(node); mstEdges.push([from!, node, weight]);

Add new node and edge to MST

for (const [neighbor, w] of graph.edges.get(node)!) { if (!visited.has(neighbor)) { minHeap.push({node: neighbor, from: node, weight: w}); } }

Add new edges from recently added node to candidates

Output

A - C: 3

C - B: 4

Total cost: 7

Complexity Analysis

Time: O(E * V) because we scan edges and select minimum edges repeatedly without a priority queue

Space: O(V + E) to store graph and candidate edges

vs Alternative: Using a priority queue reduces time to O(E log V), making this simpler approach less efficient but easier to understand

Edge Cases

Graph with single node and no edges

Returns empty MST since no edges to add

DSA Typescript

visited.add(start);

Disconnected graph

MST includes only connected component of start node; others remain unconnected

DSA Typescript

while (minHeap.length > 0 && visited.size < graph.nodes.length)

Multiple edges with same weight

Algorithm picks any minimal edge; MST remains valid

DSA Typescript

const {node, from, weight} = extractMin();

When to Use This Pattern

When asked to connect all points with minimum total cost and no cycles, reach for Prim's MST algorithm because it grows the tree by always choosing the cheapest connecting edge.

Common Mistakes

Mistake: Not marking nodes as visited before adding their edges, causing cycles
Fix: Add node to visited set immediately after selecting its connecting edge

Mistake: Not updating candidate edges after adding a new node
Fix: Add all edges from the newly added node to the candidate list

Summary

Builds a tree connecting all nodes with minimum total edge cost by growing from a start node.

Use when you need the cheapest way to connect all points without cycles.

Always pick the smallest edge connecting the current tree to a new node to keep cost minimal.