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.

Practice

1. What is the main goal of Prim's algorithm in graph theory?

easy

A. To find the minimum spanning tree connecting all vertices with the least total edge weight

B. To find the shortest path between two vertices

C. To detect cycles in a graph

D. To sort vertices based on their degree

Solution

1. Step 1: Understand Prim's algorithm purpose

   Prim's algorithm builds a tree connecting all vertices with minimum total edge weight.

2. Step 2: Compare with other graph algorithms

   Shortest path and cycle detection are different problems; Prim's focuses on spanning tree.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices with the least total edge weight -> Option A

4. Quick Check:

   Prim's algorithm = Minimum Spanning Tree [OK]

Hint: Prim's always finds minimum spanning tree, not shortest path [OK]

Common Mistakes:

• Confusing Prim's with Dijkstra's algorithm
• Thinking it finds shortest path
• Assuming it detects cycles

2. Which of the following is the correct way to initialize the key array in Prim's algorithm in TypeScript?

easy

A. const key: number[] = Array(n).fill(0);

B. const key: number[] = new Array(n).fill(Infinity);

C. const key: number[] = new Array(n).fill(null);

D. const key: number[] = Array(n).fill(-1);

Solution

1. Step 1: Understand key array role

   Key array stores minimum edge weights; initialize with Infinity to find minimum.

2. Step 2: Check initialization options

   Filling with Infinity ensures any edge weight will be smaller initially.

3. Final Answer:

   const key: number[] = new Array(n).fill(Infinity); -> Option B

4. Quick Check:

   Initialize keys with Infinity for minimum comparison [OK]

Hint: Use Infinity to initialize keys for minimum edge weight tracking [OK]

Common Mistakes:

• Initializing keys with 0 causes wrong minimum comparisons
• Using null instead of a number
• Filling with -1 which is invalid for weights

3. Consider the following TypeScript code snippet implementing Prim's algorithm on a graph with 4 vertices. What is the printed MST total weight?

const graph = [
  [0, 2, 0, 6],
  [2, 0, 3, 8],
  [0, 3, 0, 0],
  [6, 8, 0, 0]
];

function primMST(graph: number[][]): number {
  const n = graph.length;
  const key = new Array(n).fill(Infinity);
  const mstSet = new Array(n).fill(false);
  key[0] = 0;
  let totalWeight = 0;

  for (let count = 0; count < n - 1; count++) {
    let min = Infinity;
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!mstSet[v] && key[v] < min) {
        min = key[v];
        u = v;
      }
    }
    mstSet[u] = true;
    totalWeight += min;

    for (let v = 0; v < n; v++) {
      if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
        key[v] = graph[u][v];
      }
    }
  }
  return totalWeight;
}

console.log(primMST(graph));

medium

A. 11

B. 9

C. 14

D. 10

Solution

1. Step 1: Trace MST selection steps

   Start with vertex 0: key[0]=0, others Infinity. Select vertex 0 (weight 0), add edges: 2 (to 1), 6 (to 3).

2. Step 2: Select next minimum edge

   Choose vertex 1 (key=2), add edge weight 2. Update keys: vertex 2 gets 3 (edge 1-2), vertex 3 remains 6.

3. Step 3: Select next minimum edge

   Choose vertex 2 (key=3), add edge weight 3. Vertex 3 key remains 6.

4. Step 4: Select last vertex

   Choose vertex 3 (key=6), add edge weight 6.

5. Step 5: Calculate total weight

   Total = 2 + 3 + 6 = 11

6. Final Answer:

   11 -> Option A

7. Quick Check:

   MST total weight = 11 [OK]

Hint: Add chosen edge weights stepwise to get MST total [OK]

Common Mistakes:

• Forgetting to add the first vertex key (0) to total
• Adding all edges instead of MST edges
• Mixing up vertex indices

4. The following TypeScript code for Prim's algorithm has a bug. What is the error?

function primMST(graph: number[][]): number {
  const n = graph.length;
  const key = new Array(n).fill(Infinity);
  const mstSet = new Array(n).fill(false);
  key[0] = 0;
  let totalWeight = 0;

  for (let count = 0; count <= n - 1; count++) {
    let min = Infinity;
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!mstSet[v] && key[v] < min) {
        min = key[v];
        u = v;
      }
    }
    mstSet[u] = true;
    totalWeight += min;

    for (let v = 0; v < n; v++) {
      if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
        key[v] = graph[u][v];
      }
    }
  }
  return totalWeight;
}

medium

A. The inner loop condition should be v <= n

B. The key array is not initialized correctly

C. The mstSet array should be initialized with true values

D. The outer loop runs one extra time causing an invalid vertex selection

Solution

1. Step 1: Analyze outer loop range

   The loop runs from 0 to n inclusive (<= n - 1), which means n iterations instead of n-1.

2. Step 2: Understand impact of extra iteration

   Extra iteration causes selection of u = -1 (no valid vertex), leading to errors or invalid updates.

3. Final Answer:

   The outer loop runs one extra time causing an invalid vertex selection -> Option D

4. Quick Check:

   Loop count must be n-1, not n [OK]

Hint: Outer loop should run n-1 times, not n [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing mstSet incorrectly
• Changing inner loop bounds wrongly

5. Given a weighted undirected graph represented by the adjacency matrix below, apply Prim's algorithm starting from vertex 0. Which edges are included in the MST?

const graph = [
  [0, 1, 4, 0, 0, 0],
  [1, 0, 4, 2, 7, 0],
  [4, 4, 0, 3, 5, 0],
  [0, 2, 3, 0, 4, 6],
  [0, 7, 5, 4, 0, 7],
  [0, 0, 0, 6, 7, 0]
];

Options list edges as pairs (u-v):

hard

A. (0-2), (2-3), (3-1), (3-4), (4-5)

B. (0-1), (1-3), (3-5), (5-4), (4-2)

C. (0-1), (1-3), (3-2), (3-4), (3-5)

D. (0-1), (1-2), (2-3), (3-4), (4-5)

Solution

1. Step 1: Start from vertex 0 and pick minimum edges

   From 0, edges: (0-1)=1, (0-2)=4. Choose (0-1) with weight 1.

2. Step 2: Update keys and select next minimum edge

   From vertices {0,1}, edges: (1-3)=2, (1-2)=4, (0-2)=4. Choose (1-3) with weight 2.

3. Step 3: Continue selecting minimum edges connecting MST

   From {0,1,3}, edges: (3-2)=3, (3-4)=4, (3-5)=6. Choose (3-2) with weight 3.

4. Step 4: Next minimum edge from MST

   From {0,1,2,3}, edges: (3-4)=4, (3-5)=6. Choose (3-4) with weight 4.

5. Step 5: Final edge to include

   From {0,1,2,3,4}, edges: (3-5)=6, (4-5)=7. Choose (3-5) with weight 6.

6. Final Answer:

   (0-1), (1-3), (3-2), (3-4), (3-5) -> Option C

7. Quick Check:

   Edges chosen minimize total weight connecting all vertices [OK]

Hint: Pick smallest connecting edge each step starting from vertex 0 [OK]

Common Mistakes:

• Choosing edges with larger weights early
• Not updating keys after adding vertices
• Assuming linear chain instead of MST shape