Minimum Spanning Tree Prim's Algorithm in DSA Javascript - Execution Trace

Concept Flow - Minimum Spanning Tree Prim's Algorithm

Start with any node

↓

Add node to MST set

↓

Find edges from MST to non-MST nodes

↓

Select edge with smallest weight

↓

Add new node to MST set

↓

Repeat until all nodes included

Start from any node, add it to MST, then repeatedly add the smallest edge connecting MST to new nodes until all nodes are included.

Execution Sample

DSA Javascript

const graph = {
  A: {B: 2, C: 3},
  B: {A: 2, C: 1, D: 4},
  C: {A: 3, B: 1, D: 5},
  D: {B: 4, C: 5}
};
// Prim's MST starting from A

Graph used to demonstrate Prim's algorithm starting from node A to find the minimum spanning tree.

Execution Table

Step	Operation	Nodes in MST	Edges Considered	Selected Edge	Visual MST State
1	Start at node A	[A]	Edges: A-B(2), A-C(3)	None yet	A
2	Select smallest edge from MST to non-MST	[A]	Edges: A-B(2), A-C(3)	A-B(2)	A --2-- B
3	Add node B to MST	[A, B]	Edges: A-C(3), B-C(1), B-D(4)	None yet	A --2-- B
4	Select smallest edge from MST to non-MST	[A, B]	Edges: A-C(3), B-C(1), B-D(4)	B-C(1)	A --2-- B --1-- C
5	Add node C to MST	[A, B, C]	Edges: B-D(4), C-D(5)	None yet	A --2-- B --1-- C
6	Select smallest edge from MST to non-MST	[A, B, C]	Edges: B-D(4), C-D(5)	B-D(4)	A --2-- B --1-- C | 4 D
7	Add node D to MST	[A, B, C, D]	Edges: None	None	A --2-- B --1-- C | 4 D
8	All nodes included, MST complete	[A, B, C, D]	None	None	Final MST as above

💡 All nodes are included in MST, algorithm stops.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
MST Nodes	[]	[A, B]	[A, B, C]	[A, B, C, D]	[A, B, C, D]
Edges Considered	[]	[A-B(2), A-C(3)]	[A-C(3), B-C(1), B-D(4)]	[B-D(4), C-D(5)]	[]
Selected Edge	None	A-B(2)	B-C(1)	B-D(4)	None

Key Moments - 3 Insights

Why do we only consider edges that connect MST nodes to non-MST nodes?

Because MST must connect all nodes without cycles, so we only add edges that expand MST to new nodes. See execution_table rows 2, 4, and 6 where edges connect MST to outside nodes.

Why does the algorithm stop when all nodes are included in MST?

Because MST must include every node exactly once connected by minimum edges. Once all nodes are in MST (row 7), no more edges are needed.

How do we know which edge to pick at each step?

We pick the edge with the smallest weight connecting MST to a new node. This is shown in execution_table rows 2, 4, and 6 where smallest edges are selected.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which edge is selected?

A A-C(3)

B B-C(1)

C B-D(4)

D C-D(5)

💡 Hint

Check the 'Selected Edge' column at step 4 in execution_table.

At which step does node D get added to the MST?

A Step 7

B Step 4

C Step 6

D Step 5

💡 Hint

Look at the 'Nodes in MST' column to see when D appears.

If the edge B-D had weight 2 instead of 4, how would the selected edge at step 6 change?

A It would still be B-D(4)

B It would be C-D(5)

C It would be B-D(2)

D No edge would be selected

💡 Hint

Compare edge weights in 'Edges Considered' at step 6.

Concept Snapshot

Prim's Algorithm builds MST by:
- Starting from any node
- Adding smallest edge connecting MST to new nodes
- Repeating until all nodes included
- Always choosing minimum weight edge to avoid cycles
- Resulting MST connects all nodes with minimum total weight

Full Transcript

Prim's algorithm for Minimum Spanning Tree starts from any node and adds it to the MST set. Then it looks at all edges connecting nodes in MST to nodes outside MST and picks the smallest edge. The node connected by this edge is added to MST. This repeats until all nodes are included. The execution table shows each step with nodes in MST, edges considered, and selected edges. The variable tracker shows how MST nodes and edges change. Key moments clarify why only edges connecting MST to non-MST nodes are considered, why the algorithm stops when all nodes are included, and how the smallest edge is chosen each time. The visual quiz tests understanding of edge selection and node addition steps. The concept snapshot summarizes the algorithm's main points for quick reference.

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