Minimum Spanning Tree Prim's Algorithm in DSA Javascript - 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 MST edges after running Prim's algorithm on the given graph?

DSA Javascript

const graph = {
  0: [{node:1, weight:2}, {node:3, weight:6}],
  1: [{node:0, weight:2}, {node:2, weight:3}, {node:3, weight:8}],
  2: [{node:1, weight:3}, {node:3, weight:7}],
  3: [{node:0, weight:6}, {node:1, weight:8}, {node:2, weight:7}]
};

function primMST(graph) {
  const mst = [];
  const visited = new Set();
  const edges = [];
  visited.add(0);
  graph[0].forEach(e => edges.push({from:0, to:e.node, weight:e.weight}));

  while (visited.size < Object.keys(graph).length) {
    edges.sort((a,b) => a.weight - b.weight);
    let edge = null;
    while (edges.length) {
      const e = edges.shift();
      if (!visited.has(e.to)) {
        edge = e;
        break;
      }
    }
    if (!edge) break;
    mst.push(edge);
    visited.add(edge.to);
    graph[edge.to].forEach(e => {
      if (!visited.has(e.node)) {
        edges.push({from: edge.to, to: e.node, weight: e.weight});
      }
    });
  }
  return mst;
}

const result = primMST(graph);
result.forEach(e => console.log(`${e.from} -> ${e.to} (weight ${e.weight})`));

A "0 -> 1 (weight 2)\n1 -> 2 (weight 3)\n0 -> 3 (weight 6)"

B "0 -> 3 (weight 6)\n3 -> 2 (weight 7)\n0 -> 1 (weight 2)"

C "0 -> 1 (weight 2)\n1 -> 3 (weight 8)\n3 -> 2 (weight 7)"

D "1 -> 0 (weight 2)\n1 -> 2 (weight 3)\n2 -> 3 (weight 7)"

💡 Hint

Start from node 0 and always pick the smallest edge connecting to an unvisited node.

Prim's algorithm starts at node 0. It picks edge 0->1 (weight 2) first, then 1->2 (weight 3), and finally 0->3 (weight 6) to connect all nodes with minimum total weight.

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Edge Selection

In Prim's algorithm, which property is used to select the next edge to add to the MST?

A The edge with the minimum weight connecting a visited node to an unvisited node

B The edge connecting two unvisited nodes with the smallest weight

C The edge with the maximum weight connecting any two nodes

D The edge with the minimum weight connecting any two nodes regardless of visited status

💡 Hint

Think about how Prim's algorithm grows the MST step by step.

Prim's algorithm always adds the smallest edge that connects a node already in the MST to a node not yet included, ensuring the MST grows without cycles and with minimum total weight.

🔧 Debug

advanced

Identify the Error in Prim's Algorithm Implementation

What error will occur when running this Prim's algorithm code snippet?

DSA Javascript

const graph = {
  0: [{node:1, weight:4}],
  1: [{node:0, weight:4}, {node:2, weight:1}],
  2: undefined
};

function primMST(graph) {
  const mst = [];
  const visited = new Set();
  const edges = [];
  visited.add(0);
  graph[0].forEach(e => edges.push({from:0, to:e.node, weight:e.weight}));

  while (visited.size < Object.keys(graph).length) {
    edges.sort((a,b) => a.weight - b.weight);
    let edge = null;
    while (edges.length) {
      const e = edges.shift();
      if (!visited.has(e.to)) {
        edge = e;
        break;
      }
    }
    if (!edge) break;
    mst.push(edge);
    visited.add(edge.to);
    graph[edge.to].forEach(e => {
      if (!visited.has(e.node)) {
        edges.push({from: edge.to, to: e.node, weight: e.weight});
      }
    });
  }
  return mst;
}

primMST(graph);

A Infinite loop due to edges not updating

B ReferenceError: edges is not defined

C TypeError: Cannot read property 'forEach' of undefined

D No error, code runs correctly

💡 Hint

Check if all nodes have neighbors defined in the graph.

Node 2 has neighbors defined, but if the graph misses any node's adjacency list, accessing graph[edge.to] may be undefined, causing a TypeError when calling forEach.

🚀 Application

advanced

Minimum Spanning Tree Weight Calculation

Given the graph below, what is the total weight of the MST found by Prim's algorithm starting at node 0?

DSA Javascript

const graph = {
  0: [{node:1, weight:10}, {node:2, weight:6}, {node:3, weight:5}],
  1: [{node:0, weight:10}, {node:3, weight:15}],
  2: [{node:0, weight:6}, {node:3, weight:4}],
  3: [{node:0, weight:5}, {node:1, weight:15}, {node:2, weight:4}]
};

A 15

B 21

C 25

D 19

💡 Hint

Add the weights of edges selected by Prim's algorithm starting from node 0.

Prim's algorithm picks edges with weights 5 (0->3), 4 (3->2), and 10 (0->1). Total weight = 5 + 4 + 10 = 19.

❓ Predict Output

expert

Prim's Algorithm on a Disconnected Graph

What will be the output when running Prim's algorithm on this disconnected graph starting from node 0?

DSA Javascript

const graph = {
  0: [{node:1, weight:1}],
  1: [{node:0, weight:1}],
  2: [{node:3, weight:2}],
  3: [{node:2, weight:2}]
};

function primMST(graph) {
  const mst = [];
  const visited = new Set();
  const edges = [];
  visited.add(0);
  graph[0].forEach(e => edges.push({from:0, to:e.node, weight:e.weight}));

  while (visited.size < Object.keys(graph).length) {
    edges.sort((a,b) => a.weight - b.weight);
    let edge = null;
    while (edges.length) {
      const e = edges.shift();
      if (!visited.has(e.to)) {
        edge = e;
        break;
      }
    }
    if (!edge) break;
    mst.push(edge);
    visited.add(edge.to);
    graph[edge.to].forEach(e => {
      if (!visited.has(e.node)) {
        edges.push({from: edge.to, to: e.node, weight: e.weight});
      }
    });
  }
  return mst;
}

const result = primMST(graph);
result.forEach(e => console.log(`${e.from} -> ${e.to} (weight ${e.weight})`));

A "2 -> 3 (weight 2)"

B "0 -> 1 (weight 1)"

C "0 -> 1 (weight 1)\n2 -> 3 (weight 2)"

D "No edges printed because graph is disconnected"

💡 Hint

Prim's algorithm only covers the connected component of the start node.

Prim's algorithm starting at node 0 only visits nodes 0 and 1 because nodes 2 and 3 are disconnected. So only edge 0->1 is included in the MST.

Practice

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

easy

A. To detect cycles in a graph

B. To find the shortest path between two nodes

C. To sort the nodes in topological order

D. To find the minimum spanning tree of a connected weighted graph

Solution

1. Step 1: Understand Prim's Algorithm purpose

   Prim's Algorithm is designed to find a tree that connects all vertices with the smallest total edge weight.

2. Step 2: Compare with other graph algorithms

   Shortest path algorithms find paths, cycle detection finds loops, and topological sort orders nodes. These are different from Prim's goal.

3. Final Answer:

   To find the minimum spanning tree of a connected weighted graph -> Option D

4. Quick Check:

   Prim's Algorithm = Minimum Spanning Tree [OK]

Hint: Prim's builds MST by adding cheapest edges stepwise [OK]

Common Mistakes:

• Confusing Prim's with shortest path algorithms
• Thinking it detects cycles
• Mixing it with topological sorting

2. Which of the following is the correct way to initialize the key array in Prim's Algorithm in JavaScript for a graph with 5 vertices?

easy

A. const key = Array(5).fill(-1); key[0] = 0;

B. const key = Array(5).fill(0); key[0] = Infinity;

C. const key = new Array(5).fill(Infinity); key[0] = 0;

D. const key = new Array(5).fill(null); key[0] = 0;

Solution

1. Step 1: Understand key array purpose

   The key array holds the minimum edge weight to connect each vertex. It starts with Infinity except the first vertex which is 0.

2. Step 2: Check initialization syntax

   Using new Array(5).fill(Infinity) sets all to Infinity, then key[0] = 0 sets start vertex correctly.

3. Final Answer:

   const key = new Array(5).fill(Infinity); key[0] = 0; -> Option C

4. Quick Check:

   Key array init with Infinity except start = 0 [OK]

Hint: Initialize keys with Infinity, start vertex key = 0 [OK]

Common Mistakes:

• Filling key array with zeros instead of Infinity
• Setting start vertex key to Infinity
• Using null or -1 which breaks comparisons

3. Consider the following adjacency matrix for a graph with 4 vertices:

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

If Prim's Algorithm starts from vertex 0, what is the order of vertices added to the MST?

medium

A. [0, 3, 1, 2]

B. [0, 1, 3, 2]

C. [0, 1, 2, 3]

D. [0, 2, 1, 3]

Solution

1. Step 1: Start from vertex 0

   Initialize MST with vertex 0. Adjacent edges: 0-1 (2), 0-3 (6).

2. Step 2: Choose minimum edge from MST

   Edge 0-1 has weight 2, edge 0-3 has weight 6. Choose vertex 1 next.

3. Step 3: Update edges from MST vertices (0,1)

   Edges: 1-2 (3), 1-3 (8), 0-3 (6). Minimum is 1-2 (3) vs 0-3 (6). Choose vertex 2 next.

4. Step 4: Add vertex 2 and update edges

   Edges from MST (0,1,2): 0-3 (6), 1-3 (8), 2-3 (0). Minimum is 0-3 (6). Add vertex 3 last.

5. Final Answer:

   [0, 1, 3, 2] -> Option B

6. Quick Check:

   Prim's MST order = [0, 1, 3, 2] [OK]

Hint: Pick smallest edge from MST vertices each step [OK]

Common Mistakes:

• Choosing edges with zero weight as valid connections
• Not updating edges after adding vertices
• Adding vertices in wrong order ignoring minimum edge

4. The following code snippet attempts to implement Prim's Algorithm but has a bug. What is the bug?

function primMST(graph) {
  const V = graph.length;
  const key = new Array(V).fill(Infinity);
  const mstSet = new Array(V).fill(false);
  key[0] = 0;

  for (let count = 0; count < V - 1; count++) {
    let u = minKey(key, mstSet);
    mstSet[u] = true;

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

function minKey(key, mstSet) {
  let min = Infinity, minIndex = -1;
  for (let v = 0; v < key.length; v++) {
    if (!mstSet[v] && key[v] < min) {
      min = key[v];
      minIndex = v;
    }
  }
  return minIndex;
}

medium

A. The function does not track parent nodes to build MST edges

B. The minKey function returns -1 if all vertices are in MST, causing errors

C. The key array is not initialized correctly with zeros

D. The graph adjacency matrix uses 0 for no edge, which causes wrong comparisons

Solution

1. Step 1: Analyze code functionality

   The code updates key values and mstSet correctly but only returns key array, not MST edges.

2. Step 2: Identify missing MST structure

   Prim's Algorithm requires tracking parent nodes to know which edges form the MST. This code lacks parent tracking.

3. Final Answer:

   The function does not track parent nodes to build MST edges -> Option A

4. Quick Check:

   Missing parent array means MST edges unknown [OK]

Hint: Track parents to know MST edges, not just keys [OK]

Common Mistakes:

• Assuming key array alone gives MST edges
• Ignoring need for parent array
• Thinking minKey returning -1 causes error here

5. Given a weighted undirected graph represented as an adjacency list:

const graph = {
  0: [{node:1, weight:4}, {node:7, weight:8}],
  1: [{node:0, weight:4}, {node:2, weight:8}, {node:7, weight:11}],
  2: [{node:1, weight:8}, {node:3, weight:7}, {node:5, weight:4}, {node:8, weight:2}],
  3: [{node:2, weight:7}, {node:4, weight:9}, {node:5, weight:14}],
  4: [{node:3, weight:9}, {node:5, weight:10}],
  5: [{node:2, weight:4}, {node:3, weight:14}, {node:4, weight:10}, {node:6, weight:2}],
  6: [{node:5, weight:2}, {node:7, weight:1}, {node:8, weight:6}],
  7: [{node:0, weight:8}, {node:1, weight:11}, {node:6, weight:1}, {node:8, weight:7}],
  8: [{node:2, weight:2}, {node:6, weight:6}, {node:7, weight:7}]
};

If you run Prim's Algorithm starting from vertex 0, which edge will be added last to the MST?

hard

A. Edge between vertices 3 and 4 with weight 9

B. Edge between vertices 4 and 5 with weight 10

C. Edge between vertices 1 and 7 with weight 11

D. Edge between vertices 7 and 8 with weight 7

Solution

1. Step 1: Understand MST construction order

   Prim's Algorithm adds edges with smallest weights connecting new vertices to MST.

2. Step 2: Identify heavy edges likely added last

   Edges with large weights like 9, 11, 10, 7 are candidates for last addition.

3. Step 3: Trace MST growth

   Starting from 0: add 1 (0-1:4), 2 (1-2:8), 8 (2-8:2), 5 (2-5:4), 6 (5-6:2), 7 (6-7:1), 3 (2-3:7), and finally 4 (3-4:9).

4. Final Answer:

   Edge between vertices 3 and 4 with weight 9 -> Option A

5. Quick Check:

   Largest edge weight added last in Prim's MST [OK]

Hint: Largest edge in MST usually added last [OK]

Common Mistakes:

• Assuming edges with weight 7 or 10 are last
• Ignoring that MST adds smallest edges first
• Confusing adjacency list with matrix