Minimum Spanning Tree Prim's Algorithm in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the MST set for Prim's algorithm.

DSA Javascript

const mstSet = new Array(V).fill([1]);

Drag options to blanks, or click blank then click option'

A0

Bnull

Cfalse

Dtrue

Attempts:

3 left

💡 Hint

Common Mistakes

Using true initially, which means all vertices are already included.

Using 0 or null which do not represent boolean inclusion.

The MST set keeps track of vertices included in MST. Initially, none are included, so all are false.

2fill in blank

medium

Complete the code to update the minimum key value for vertex v.

DSA Javascript

if (graph[u][v] && mstSet[v] === false && graph[u][v] < key[[1]]) {
  key[v] = graph[u][v];
  parent[v] = u;
}

Drag options to blanks, or click blank then click option'

Av

Bu

Cparent[v]

Dkey[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Using u instead of v in key array comparison.

Comparing with parent[v] or key[u] which are incorrect.

We compare the new edge weight with the current key value of vertex v to update it.

3fill in blank

hard

Fix the error in the function that finds the vertex with minimum key value not yet included in MST.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

AminIndex

Bmin

Ckey[v]

DInfinity

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing key[v] with minIndex which is an index, not a value.

Comparing with Infinity which is always larger.

We compare key[v] with the current minimum value stored in min to find the smallest key.

4fill in blank

hard

Fill both blanks to complete the loop that constructs the MST result string.

DSA Javascript

let result = '';
for (let i = 1; i < V; i++) {
  result += parent[i] + ' - ' + [1] + ': ' + [2] + '\n';
}

Drag options to blanks, or click blank then click option'

Ai

Bgraph[parent[i]][i]

Cparent[i]

Dkey[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Using key[i] which may not represent the actual edge weight.

Using parent[i] twice instead of i for the destination vertex.

We print edges from parent[i] to i with their weights from the graph adjacency matrix.

5fill in blank

hard

Fill all three blanks to complete the Prim's algorithm main loop updating MST and keys.

DSA Javascript

for (let count = 0; count < V - 1; count++) {
  let u = minKey(key, mstSet);
  mstSet[[1]] = true;
  for (let v = 0; v < V; v++) {
    if (graph[u][v] && mstSet[v] === false && graph[u][v] < [2]) {
      parent[v] = u;
      key[v] = graph[u][v];
    }
  }
}

Drag options to blanks, or click blank then click option'

Au

Bkey[v]

DmstSet[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Marking mstSet[v] instead of mstSet[u].

Comparing with mstSet[v] instead of key[v].

We mark vertex u as included in MST, then update key[v] if a smaller edge is found.

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