Why Minimum Spanning Tree Prim's Algorithm in DSA Typescript?

The Big Idea

What if you could connect all cities with the least road length without checking every possible path?

The Scenario

Imagine you have a map of cities connected by roads, and you want to connect all cities with the least total road length. Doing this by checking every possible road combination manually would be like trying to find the shortest path through a huge maze without any clues.

The Problem

Manually checking all road connections is slow and confusing. You might miss shorter routes or accidentally pick longer roads. It's easy to get lost in the many options and make mistakes, wasting time and effort.

The Solution

Prim's Algorithm helps by starting from one city and always picking the shortest road to a new city not yet connected. It builds the best network step-by-step, avoiding mistakes and saving time.

Before vs After

✗ Before

let roads = [...];
// Check all combinations manually
// Calculate total length for each
// Pick the shortest network

✓ After

function primMST(graph) {
  // Start from one node
  // Pick shortest edge to new node
  // Repeat until all nodes connected
}

What It Enables

It enables building the cheapest network connecting all points efficiently and reliably.

Real Life Example

Designing a network of power lines to connect all houses with minimum cable length and cost.

Key Takeaways

Manual checking of all connections is slow and error-prone.

Prim's Algorithm builds the minimum network step-by-step by choosing the shortest next connection.

This method saves time and ensures the cheapest total connection.

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