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

Prim's algorithm starts from one node, adds the smallest edge connecting to a new node, and repeats until all nodes are included in the MST.

Execution Sample

DSA Java

int[] key = new int[V];
boolean[] mstSet = new boolean[V];
for (int i = 0; i < V; i++) {
  key[i] = Integer.MAX_VALUE;
}
key[0] = 0;
for (int count = 0; count < V - 1; count++) {
  int u = minKey(key, mstSet);
  mstSet[u] = true;
  updateKeys(u, key, mstSet);
}

This code initializes keys, picks the minimum key node not in MST, adds it, and updates keys for adjacent nodes.

Execution Table

Step	Operation	Nodes in MST Set	Minimum Edge Selected	Visual State (MST edges)
1	Start with node 0	[0]	None (start node)	0
2	Select min edge from 0	[0, 1]	Edge 0-1 (weight 2)	0 --2-- 1
3	Select min edge from MST nodes	[0, 1, 2]	Edge 0-2 (weight 3)	0 --2-- 1 | 3
4	Select min edge from MST nodes	[0, 1, 2, 4]	Edge 2-4 (weight 4)	0 --2-- 1 | 3 --4-- 4
5	Select min edge from MST nodes	[0, 1, 2, 4, 3]	Edge 1-3 (weight 6)	0 --2-- 1 --6-- 3 | 3 --4-- 4
6	All nodes included	[0, 1, 2, 4, 3]	None	Final MST: 0-1, 1-3, 0-2, 2-4

💡 All nodes are included in MST, algorithm stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
key	[∞, ∞, ∞, ∞, ∞]	[0, 2, 3, ∞, ∞]	[0, 2, 3, 6, ∞]	[0, 2, 3, 6, 4]	[0, 2, 3, 6, 4]	[0, 2, 3, 6, 4]	[0, 2, 3, 6, 4]
mstSet	[false, false, false, false, false]	[true, false, false, false, false]	[true, true, false, false, false]	[true, true, true, false, false]	[true, true, true, false, true]	[true, true, true, true, true]	[true, true, true, true, true]

Key Moments - 3 Insights

Why do we start with key[0] = 0 and others as infinity?

Setting key[0] = 0 ensures the algorithm starts from node 0, picking it first as shown in execution_table step 1. Other keys are infinity to indicate they are not yet connected.

Why do we update keys only for nodes not in MST?

Keys represent minimum edge weights to nodes outside MST. Updating keys only for non-MST nodes ensures we always pick the smallest edge connecting MST to new nodes, as seen in variable_tracker key updates.

How does the algorithm know when to stop?

The algorithm stops when all nodes are included in mstSet (true), as shown in execution_table step 6 and variable_tracker mstSet final state.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, which edge is selected to add node 2 to MST?

A Edge 2-4 (weight 4)

B Edge 0-2 (weight 3)

C Edge 1-3 (weight 6)

D Edge 0-1 (weight 2)

💡 Hint

Check the 'Minimum Edge Selected' column at Step 3 in execution_table.

At which step does node 4 get included in the MST set?

A Step 4

B Step 5

C Step 2

D Step 3

💡 Hint

Look at 'Nodes in MST Set' column in execution_table and see when 4 appears.

According to variable_tracker, what is the key value of node 2 after Step 2?

A 6

B ∞ (infinity)

C 3

D 2

💡 Hint

Check the 'key' row under 'After Step 2' column in variable_tracker.

Concept Snapshot

Prim's Algorithm for MST:
- Start from any node (key=0), others key=∞
- Pick node with smallest key not in MST
- Add node to MST set
- Update keys of adjacent nodes
- Repeat until all nodes included
- Result: MST with minimum total edge weight

Full Transcript

Prim's algorithm builds a minimum spanning tree by starting from a chosen node with key 0 and others set to infinity. It repeatedly selects the node with the smallest key not yet in the MST set, adds it to the MST, and updates the keys of its adjacent nodes to reflect the smallest edge connecting them to the MST. This process continues until all nodes are included in the MST set. The execution table shows each step's MST nodes, selected edges, and the visual MST state. The variable tracker records the key values and MST membership after each step. Key moments clarify why keys start as they do, why updates only affect non-MST nodes, and when the algorithm stops. The visual quiz tests understanding of edge selection, node inclusion timing, and key values during execution.

Practice

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

easy

A. To sort vertices based on their degree

B. To find the shortest path between two vertices

C. To detect cycles in a graph

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

Solution

1. Step 1: Understand Prim's Algorithm purpose

   Prim's Algorithm builds a tree connecting all vertices with the smallest sum of edge weights.

2. Step 2: Compare with other graph tasks

   It is not for shortest path, cycle detection, or sorting vertices.

3. Final Answer:

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

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 paths
• Assuming it detects cycles

2. Which of the following Java code snippets correctly initializes the key array for Prim's Algorithm for a graph with 5 vertices?

easy

A. int key[] = new int[5]; for(int i=0; i<5; i++) key[i] = 0;

B. int[] key = new int[5]; Arrays.fill(key, 0); key[0] = Integer.MAX_VALUE;

C. int[] key = new int[5]; Arrays.fill(key, Integer.MAX_VALUE); key[0] = 0;

D. int[] key = new int[5]; key[0] = Integer.MIN_VALUE; Arrays.fill(key, Integer.MAX_VALUE);

Solution

1. Step 1: Understand key array initialization

   Key array stores minimum edge weights to vertices; initialize with max values except start vertex 0 with 0.

2. Step 2: Check each option

   int[] key = new int[5]; Arrays.fill(key, Integer.MAX_VALUE); key[0] = 0; correctly sets all to Integer.MAX_VALUE and start vertex key[0] to 0.

3. Final Answer:

   int[] key = new int[5]; Arrays.fill(key, Integer.MAX_VALUE); key[0] = 0; -> Option C

4. Quick Check:

   Initialize keys with max except start = 0 [OK]

Hint: Start vertex key = 0, others = max value [OK]

Common Mistakes:

• Setting all keys to 0
• Setting start vertex key to max value
• Incorrect order of fill and assignment

3. Given the following adjacency matrix for a graph with 4 vertices, what is the total weight of the minimum spanning tree found by Prim's Algorithm starting from vertex 0?

int[][] graph = {
  {0, 2, 0, 6},
  {2, 0, 3, 8},
  {0, 3, 0, 0},
  {6, 8, 0, 0}
};

medium

A. 14

B. 11

C. 9

D. 10

Solution

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

   Edges chosen: 0-1 (2), 1-2 (3), 0-3 (6)

2. Step 2: Sum the weights of chosen edges

   Total weight = 2 + 3 + 6 = 11

3. Final Answer:

   11 -> Option B

4. Quick Check:

   Sum edges 2+3+6 = 11 [OK]

Hint: Add weights of edges chosen by Prim's stepwise [OK]

Common Mistakes:

• Choosing wrong edges ignoring minimum weight
• Adding edges that form cycles
• Starting from wrong vertex

4. Identify the error in the following Java code snippet implementing Prim's Algorithm and select the correct fix:

int minKey(int[] key, boolean[] mstSet) {
  int min = Integer.MAX_VALUE, minIndex = -1;
  for (int v = 0; v < key.length; v++) {
    if (!mstSet[v] && key[v] < min) {
      min = key[v];
      minIndex = v;
    }
  }
  return minIndex;
}

// Usage in main loop:
int u = minKey(key, mstSet);
mstSet[u] = true;

medium

A. No error; code correctly finds vertex with minimum key not in MST

B. minIndex should be initialized to 0 instead of -1

C. Return type should be void instead of int

D. The loop should start from 1 instead of 0

Solution

1. Step 1: Analyze minKey function logic

   It finds vertex with smallest key not yet included in MST correctly.

2. Step 2: Check initialization and loop

   minIndex = -1 is correct to detect no valid vertex; loop from 0 covers all vertices.

3. Final Answer:

   No error; code correctly finds vertex with minimum key not in MST -> Option A

4. Quick Check:

   minKey returns correct vertex index [OK]

Hint: minIndex = -1 signals no vertex found yet, loop from 0 covers all [OK]

Common Mistakes:

• Changing minIndex initialization incorrectly
• Changing return type wrongly
• Starting loop from 1 misses vertex 0

5. You have a weighted undirected graph with 6 vertices and the following edges:

0-1: 3, 0-3: 1, 1-2: 7, 1-4: 5, 2-4: 2, 3-4: 4, 3-5: 6, 4-5: 8

Using Prim's Algorithm starting from vertex 0, what is the total weight of the minimum spanning tree?

hard

A. 16

B. 15

C. 19

D. 21

Solution

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

   Edges chosen: 0-3 (1), 0-1 (3), 3-4 (4), 4-2 (2), 3-5 (6)

2. Step 2: Sum the weights of chosen edges

   Total weight = 1 + 3 + 4 + 2 + 6 = 16

3. Step 3: Check for better MST

   Replacing 3-5 (6) with 4-5 (8) is heavier; so total is 16

4. Final Answer:

   16 -> Option A

5. Quick Check:

   Sum edges 1+3+4+2+6 = 16 [OK]

Hint: Pick smallest edges connecting new vertices stepwise [OK]

Common Mistakes:

• Choosing heavier edges unnecessarily
• Missing to update keys after adding vertices
• Not starting from vertex 0