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

The Big Idea

What if you could always find the cheapest way to connect everything without guessing?

The Scenario

Imagine you have a map of cities connected by roads with different lengths. You want to connect all cities with the shortest total road length possible, but you try to do it by guessing which roads to pick one by one.

The Problem

Picking roads by guessing is slow and confusing. You might pick long roads first or create loops, wasting time and money. It's easy to make mistakes and miss the best way to connect all cities.

The Solution

Prim's Algorithm helps by starting from one city and always choosing the shortest road that connects a new city. It builds the best network step by step without loops, saving time and ensuring the shortest total road length.

Before vs After

✗ Before

let roads = [...];
// Guess roads one by one
let chosenRoads = [];
// No clear way to pick shortest roads automatically

✓ After

function primMST(graph) {
  // Start from one city
  // Pick shortest connecting road each step
  // Build minimum spanning tree
}

What It Enables

It enables building the cheapest network connecting all points without wasting resources or creating loops.

Real Life Example

Designing a network of cables to connect computers in an office with the least amount of cable used.

Key Takeaways

Manual guessing is slow and error-prone for connecting points efficiently.

Prim's Algorithm picks the shortest connection step by step to build the best network.

This method saves time, money, and avoids loops in the network.

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