Minimum Spanning Tree Prim's Algorithm in DSA Typescript - 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 minimum weight

↓

Add connected node to MST

↓

Repeat until all nodes in MST

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

Execution Sample

DSA Typescript

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}
};
// Run Prim's MST starting from A

This code runs Prim's algorithm on a graph with nodes A, B, C, D and weighted edges.

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)	Select A-B(2)	A --2-- B
2	Add node B	[A, B]	Edges: B-C(1), B-D(4), A-C(3)	Select B-C(1)	A --2-- B --1-- C
3	Add node C	[A, B, C]	Edges: C-D(5), B-D(4)	Select B-D(4)	A --2-- B --1-- C | 4 D
4	Add node D	[A, B, C, D]	No edges left	None	A --2-- B --1-- C | 4 D
5	All nodes included	[A, B, C, D]	None	Stop	Final MST as above

💡 All nodes are included in MST, algorithm stops.

Variable Tracker

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

Key Moments - 3 Insights

Why do we add edges from all MST nodes, not just the last added node?

Because MST can connect to any node outside MST from any node inside MST, as shown in step 2 where edges from both A and B are considered (execution_table row 2).

Why do we stop when all nodes are included in MST?

Because MST must span all nodes without cycles, so once all nodes are in MST (step 5), no more edges are needed (execution_table row 5).

What if multiple edges have the same minimum weight?

Prim's algorithm can pick any one of them; the MST remains valid. This example picks the first minimum edge found (execution_table rows 1-3).

Visual Quiz - 3 Questions

Look at the execution table, which edge is selected at step 3?

A A-C(3)

B B-C(1)

C B-D(4)

D C-D(5)

💡 Hint

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

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

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

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

If the edge B-D had weight 2 instead of 4, which edge would be selected at step 3?

A B-D(2)

B C-D(5)

C B-C(1)

D A-C(3)

💡 Hint

Compare edge weights at step 3 in the execution_table and consider the minimum.

Concept Snapshot

Prim's Algorithm builds MST by:
- Starting from any node
- Adding the smallest edge connecting MST to new nodes
- Repeating until all nodes included
- Always consider edges from all MST nodes
- Stops when MST spans all nodes

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 inside MST to nodes outside MST and selects the edge with the smallest weight. The connected node is added to MST. This repeats until all nodes are included. The execution table shows step-by-step which edges are considered and selected, and how the MST grows. Key points include considering edges from all MST nodes, stopping when all nodes are included, and handling ties in edge weights. The variable tracker shows MST nodes and edges considered after each step. The visual quiz tests understanding of edge selection and MST growth.

Practice

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

easy

A. To find the minimum spanning tree connecting all vertices with the least total edge weight

B. To find the shortest path between two vertices

C. To detect cycles in a graph

D. To sort vertices based on their degree

Solution

1. Step 1: Understand Prim's algorithm purpose

   Prim's algorithm builds a tree connecting all vertices with minimum total edge weight.

2. Step 2: Compare with other graph algorithms

   Shortest path and cycle detection are different problems; Prim's focuses on spanning tree.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices with the least total edge weight -> Option A

4. Quick Check:

   Prim's algorithm = Minimum Spanning Tree [OK]

Hint: Prim's always finds minimum spanning tree, not shortest path [OK]

Common Mistakes:

• Confusing Prim's with Dijkstra's algorithm
• Thinking it finds shortest path
• Assuming it detects cycles

2. Which of the following is the correct way to initialize the key array in Prim's algorithm in TypeScript?

easy

A. const key: number[] = Array(n).fill(0);

B. const key: number[] = new Array(n).fill(Infinity);

C. const key: number[] = new Array(n).fill(null);

D. const key: number[] = Array(n).fill(-1);

Solution

1. Step 1: Understand key array role

   Key array stores minimum edge weights; initialize with Infinity to find minimum.

2. Step 2: Check initialization options

   Filling with Infinity ensures any edge weight will be smaller initially.

3. Final Answer:

   const key: number[] = new Array(n).fill(Infinity); -> Option B

4. Quick Check:

   Initialize keys with Infinity for minimum comparison [OK]

Hint: Use Infinity to initialize keys for minimum edge weight tracking [OK]

Common Mistakes:

• Initializing keys with 0 causes wrong minimum comparisons
• Using null instead of a number
• Filling with -1 which is invalid for weights

3. Consider the following TypeScript code snippet implementing Prim's algorithm on a graph with 4 vertices. What is the printed MST total weight?

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

function primMST(graph: number[][]): number {
  const n = graph.length;
  const key = new Array(n).fill(Infinity);
  const mstSet = new Array(n).fill(false);
  key[0] = 0;
  let totalWeight = 0;

  for (let count = 0; count < n - 1; count++) {
    let min = Infinity;
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!mstSet[v] && key[v] < min) {
        min = key[v];
        u = v;
      }
    }
    mstSet[u] = true;
    totalWeight += min;

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

console.log(primMST(graph));

medium

A. 11

B. 9

C. 14

D. 10

Solution

1. Step 1: Trace MST selection steps

   Start with vertex 0: key[0]=0, others Infinity. Select vertex 0 (weight 0), add edges: 2 (to 1), 6 (to 3).

2. Step 2: Select next minimum edge

   Choose vertex 1 (key=2), add edge weight 2. Update keys: vertex 2 gets 3 (edge 1-2), vertex 3 remains 6.

3. Step 3: Select next minimum edge

   Choose vertex 2 (key=3), add edge weight 3. Vertex 3 key remains 6.

4. Step 4: Select last vertex

   Choose vertex 3 (key=6), add edge weight 6.

5. Step 5: Calculate total weight

   Total = 2 + 3 + 6 = 11

6. Final Answer:

   11 -> Option A

7. Quick Check:

   MST total weight = 11 [OK]

Hint: Add chosen edge weights stepwise to get MST total [OK]

Common Mistakes:

• Forgetting to add the first vertex key (0) to total
• Adding all edges instead of MST edges
• Mixing up vertex indices

4. The following TypeScript code for Prim's algorithm has a bug. What is the error?

function primMST(graph: number[][]): number {
  const n = graph.length;
  const key = new Array(n).fill(Infinity);
  const mstSet = new Array(n).fill(false);
  key[0] = 0;
  let totalWeight = 0;

  for (let count = 0; count <= n - 1; count++) {
    let min = Infinity;
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!mstSet[v] && key[v] < min) {
        min = key[v];
        u = v;
      }
    }
    mstSet[u] = true;
    totalWeight += min;

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

medium

A. The inner loop condition should be v <= n

B. The key array is not initialized correctly

C. The mstSet array should be initialized with true values

D. The outer loop runs one extra time causing an invalid vertex selection

Solution

1. Step 1: Analyze outer loop range

   The loop runs from 0 to n inclusive (<= n - 1), which means n iterations instead of n-1.

2. Step 2: Understand impact of extra iteration

   Extra iteration causes selection of u = -1 (no valid vertex), leading to errors or invalid updates.

3. Final Answer:

   The outer loop runs one extra time causing an invalid vertex selection -> Option D

4. Quick Check:

   Loop count must be n-1, not n [OK]

Hint: Outer loop should run n-1 times, not n [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing mstSet incorrectly
• Changing inner loop bounds wrongly

5. Given a weighted undirected graph represented by the adjacency matrix below, apply Prim's algorithm starting from vertex 0. Which edges are included in the MST?

const graph = [
  [0, 1, 4, 0, 0, 0],
  [1, 0, 4, 2, 7, 0],
  [4, 4, 0, 3, 5, 0],
  [0, 2, 3, 0, 4, 6],
  [0, 7, 5, 4, 0, 7],
  [0, 0, 0, 6, 7, 0]
];

Options list edges as pairs (u-v):

hard

A. (0-2), (2-3), (3-1), (3-4), (4-5)

B. (0-1), (1-3), (3-5), (5-4), (4-2)

C. (0-1), (1-3), (3-2), (3-4), (3-5)

D. (0-1), (1-2), (2-3), (3-4), (4-5)

Solution

1. Step 1: Start from vertex 0 and pick minimum edges

   From 0, edges: (0-1)=1, (0-2)=4. Choose (0-1) with weight 1.

2. Step 2: Update keys and select next minimum edge

   From vertices {0,1}, edges: (1-3)=2, (1-2)=4, (0-2)=4. Choose (1-3) with weight 2.

3. Step 3: Continue selecting minimum edges connecting MST

   From {0,1,3}, edges: (3-2)=3, (3-4)=4, (3-5)=6. Choose (3-2) with weight 3.

4. Step 4: Next minimum edge from MST

   From {0,1,2,3}, edges: (3-4)=4, (3-5)=6. Choose (3-4) with weight 4.

5. Step 5: Final edge to include

   From {0,1,2,3,4}, edges: (3-5)=6, (4-5)=7. Choose (3-5) with weight 6.

6. Final Answer:

   (0-1), (1-3), (3-2), (3-4), (3-5) -> Option C

7. Quick Check:

   Edges chosen minimize total weight connecting all vertices [OK]

Hint: Pick smallest connecting edge each step starting from vertex 0 [OK]

Common Mistakes:

• Choosing edges with larger weights early
• Not updating keys after adding vertices
• Assuming linear chain instead of MST shape