Minimum Spanning Tree Prim's Algorithm in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prim's Algorithm on a Small Graph

What is the printed state of the minimum spanning tree edges after running Prim's algorithm starting from node 0 on this graph?

DSA Typescript

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

function primMST(graph: number[][]): string {
  const V = graph.length;
  const key = Array(V).fill(Infinity);
  const parent = Array(V).fill(-1);
  const mstSet = Array(V).fill(false);

  key[0] = 0;

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

    mstSet[u] = true;

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

  let result = '';
  for (let i = 1; i < V; i++) {
    result += `${parent[i]} - ${i} | `;
  }
  return result.trim();
}

console.log(primMST(graph));

A 0 - 1 | 1 - 2 | 0 - 3 | 1 - 4 |

B 0 - 1 | 0 - 2 | 0 - 3 | 0 - 4 |

C 0 - 1 | 1 - 2 | 3 - 4 | 0 - 3 |

D 1 - 0 | 2 - 1 | 3 - 0 | 4 - 1 |

💡 Hint

Trace the algorithm step-by-step, always picking the smallest edge connecting the MST set to a new vertex.

Prim's algorithm starts from node 0, picks edges with minimum weight connecting to new nodes. The edges chosen are 0-1 (2), 1-2 (3), 0-3 (6), and 1-4 (5).

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Data Structures

Which data structure is primarily used in Prim's algorithm to efficiently select the next edge with the smallest weight?

A Stack

B Hash Table

C Queue

D Priority Queue (Min-Heap)

💡 Hint

Think about how to always pick the smallest edge quickly.

Prim's algorithm uses a priority queue (min-heap) to pick the edge with the smallest weight efficiently at each step.

🔧 Debug

advanced

Identify the Bug in Prim's Algorithm Implementation

What error will this code produce when running Prim's algorithm on a graph with disconnected components?

DSA Typescript

function primMST(graph: number[][]): number[] {
  const V = graph.length;
  const key = Array(V).fill(Infinity);
  const parent = Array(V).fill(-1);
  const mstSet = Array(V).fill(false);

  key[0] = 0;

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

    mstSet[u] = true;

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

  return parent;
}

A Infinite loop because u remains -1 when graph is disconnected

B TypeError when comparing Infinity with number

C RuntimeError due to accessing undefined index

D No error, returns MST for disconnected graph

💡 Hint

Consider what happens if no vertex is reachable from the current MST set.

If the graph has disconnected components, the inner loop may not find a vertex u with key less than Infinity, leaving u = -1. Then mstSet[-1] = true causes logical error or infinite loop.

❓ Predict Output

advanced

Prim's Algorithm Output with Edge Weights and Parent Array

What is the final parent array after running Prim's algorithm on this graph starting from node 0?

DSA Typescript

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]
];

function primMST(graph: number[][]): number[] {
  const V = graph.length;
  const key = Array(V).fill(Infinity);
  const parent = Array(V).fill(-1);
  const mstSet = Array(V).fill(false);

  key[0] = 0;

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

    mstSet[u] = true;

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

  return parent;
}

console.log(primMST(graph));

A [-1, 0, 1, 3, 1, 3]

B [-1, 0, 1, 1, 3, 3]

C [-1, 0, 0, 1, 2, 3]

D [-1, 0, 1, 2, 3, 4]

💡 Hint

Follow the selection of edges with minimum weights step-by-step.

The MST edges connect nodes as: 0-1, 1-3, 1-2, 3-4, 3-5. So parents are: 1's parent 0, 3's parent 1, 2's parent 1, 4's parent 3, 5's parent 3.

🧠 Conceptual

expert

Time Complexity of Prim's Algorithm with Different Data Structures

What is the time complexity of Prim's algorithm when implemented using an adjacency matrix and a simple array to find the minimum key?

A O(V + E)

B O(E log V)

C O(V^2)

D O(V log V + E)

💡 Hint

Consider how many times you scan all vertices to find the minimum key.

Using an adjacency matrix and scanning all vertices to find the minimum key each time results in O(V^2) time complexity.

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