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.