Minimum Spanning Tree Prim's Algorithm in DSA Javascript

Mental Model

Start from any node and keep adding the cheapest edge that connects a new node to the growing tree until all nodes are included.

Analogy: Imagine building a road network connecting all cities with the least total cost by always choosing the shortest new road from the cities already connected.

Graph:
  (A)
 /   \
5     3
/       \
(B)---4---(C)

Start at node A, tree grows by picking smallest edge connecting new nodes.

Dry Run Walkthrough

Input: Graph with nodes A, B, C and edges: A-B=5, A-C=3, B-C=4; start from node A

Goal: Build a tree connecting all nodes with minimum total edge weight

Step 1: Start from node A, add A to MST set

MST nodes: [A]
Edges considered: A-B(5), A-C(3)

Why: We begin from A to start building the tree

Step 2: Pick smallest edge from A: A-C with weight 3, add C to MST

MST nodes: [A, C]
Edges considered: A-B(5), C-B(4)

Why: Choose cheapest edge connecting new node to MST

Step 3: Pick smallest edge connecting MST to new node: C-B with weight 4, add B to MST

MST nodes: [A, C, B]
All nodes connected

Why: Add last node with minimum cost edge

Result:

MST edges: A-C(3) -> C-B(4)
Total cost: 7

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.adj = new Map();
    for (let i = 0; i < vertices.length; i++) {
      this.adj.set(vertices[i], []);
    }
  }

  addEdge(u, v, w) {
    this.adj.get(u).push({node: v, weight: w});
    this.adj.get(v).push({node: u, weight: w});
  }

  primMST(start) {
    const mstSet = new Set();
    const key = new Map();
    const parent = new Map();

    for (const vertex of this.adj.keys()) {
      key.set(vertex, Infinity);
      parent.set(vertex, null);
    }

    key.set(start, 0);

    while (mstSet.size < this.V.length) {
      // Pick vertex u not in MST with smallest key
      let u = null;
      let minKey = Infinity;
      for (const vertex of this.adj.keys()) {
        if (!mstSet.has(vertex) && key.get(vertex) < minKey) {
          minKey = key.get(vertex);
          u = vertex;
        }
      }

      if (u === null) {
        break;
      }

      mstSet.add(u); // Add u to MST

      // Update keys of adjacent vertices
      for (const neighbor of this.adj.get(u)) {
        if (!mstSet.has(neighbor.node) && neighbor.weight < key.get(neighbor.node)) {
          key.set(neighbor.node, neighbor.weight); // Update to smaller edge
          parent.set(neighbor.node, u); // Track MST connection
        }
      }
    }

    // Print MST edges and total cost
    let totalWeight = 0;
    for (const vertex of this.V) {
      if (parent.get(vertex) !== null) {
        const w = key.get(vertex);
        console.log(`${parent.get(vertex)} - ${vertex} : ${w}`);
        totalWeight += w;
      }
    }
    console.log(`Total cost: ${totalWeight}`);
  }
}

// Driver code
const vertices = ['A', 'B', 'C'];
const g = new Graph(vertices);
g.addEdge('A', 'B', 5);
g.addEdge('A', 'C', 3);
g.addEdge('B', 'C', 4);
g.primMST('A');

key.set(start, 0);

Initialize start node key to 0 to pick it first

for (const vertex of this.adj.keys()) { if (!mstSet.has(vertex) && key.get(vertex) < minKey) { minKey = key.get(vertex); u = vertex; } }

Select next node with smallest key not yet in MST

mstSet.add(u);

Add selected node to MST set

for (const neighbor of this.adj.get(u)) { if (!mstSet.has(neighbor.node) && neighbor.weight < key.get(neighbor.node)) { key.set(neighbor.node, neighbor.weight); parent.set(neighbor.node, u); } }

Update keys and parents for neighbors if cheaper edge found

Output

A - C : 3

C - B : 4

Total cost: 7

Complexity Analysis

Time: O(V^2) because for each vertex we scan all vertices to find the minimum key node

Space: O(V + E) to store adjacency list and auxiliary maps for keys and parents

vs Alternative: Compared to Kruskal's algorithm which sorts edges O(E log E), Prim's with adjacency matrix is simpler but slower for dense graphs

Edge Cases

Graph with single node

MST is just the single node with no edges

DSA Javascript

while (mstSet.size < this.V.length) { ... } handles zero edges gracefully

Disconnected graph

Algorithm will only build MST for connected component containing start node

DSA Javascript

while (mstSet.size < this.V.length) { ... } loop stops when no reachable nodes remain

Multiple edges with same weight

Algorithm picks any minimal edge; MST may vary but total cost remains minimal

DSA Javascript

if (neighbor.weight < key.get(neighbor.node)) { ... } updates keys only if strictly smaller

When to Use This Pattern

When you need to connect all points with minimum total cost and can grow the solution step-by-step by adding the cheapest connection, use Prim's MST algorithm.

Common Mistakes

Mistake: Not updating the key and parent maps when a cheaper edge is found
Fix: Always check neighbors and update key and parent if a smaller edge weight is found

Mistake: Starting from a node not in the graph
Fix: Ensure the start node exists in the graph before running the algorithm

Summary

Builds a minimum cost tree connecting all nodes by growing from a start node using cheapest edges.

Use when you want a minimum spanning tree and can add nodes one by one based on edge costs.

The key insight is to always pick the smallest edge connecting a new node to the existing tree.

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