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

Concept Flow - Minimum Spanning Tree Prim's Algorithm

Start with any node

↓

Add node to MST set

↓

Update edges to nodes not in MST

↓

Select edge with minimum weight to new node

↓

Add new node to MST set

↓

Repeat until all nodes included

↓

Minimum Spanning Tree complete

Prim's algorithm starts from any node, grows the MST by adding the closest node not yet included, and repeats until all nodes are connected.

Execution Sample

DSA C

int primMST(int graph[V][V]) {
  int parent[V];
  int key[V];
  bool mstSet[V];
  // Initialize keys and mstSet
  // Pick minimum key vertex not in mstSet
  // Update keys and parent for adjacent vertices
  // Repeat until MST complete
}

This code finds the minimum spanning tree of a graph using Prim's algorithm.

Execution Table

Step	Operation	Current MST Nodes	Edge Selected (u-v)	Updated Keys	Visual MST State
1	Start at node 0	[0]	None	[0, ∞, ∞, ∞]	0
2	Select edge with min key	[0,1]	0-1 (2)	[0,2, ∞, ∞]	0 --2-- 1
3	Select edge with min key	[0,1,3]	1-3 (6)	[0,2, ∞,6]	0 --2-- 1 | 6 3
4	Select edge with min key	[0,1,3,2]	0-2 (3)	[0,2,3,6]	0 --2-- 1 | | 3 6 2 3
5	All nodes included	[0,1,3,2]	None	[0,2,3,6]	MST Complete: 0 --2-- 1 | | 3 6 2 3
Exit	All nodes included in MST	[0,1,3,2]	None	[0,2,3,6]	Algorithm stops

💡 All nodes are included in MST, so the algorithm stops.

Variable Tracker

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

Key Moments - 3 Insights

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

Because nodes already in MST are connected; updating keys for them is unnecessary. See execution_table rows 2-4 where keys update only for nodes outside MST.

How do we pick the next node to add to MST?

We pick the node with the smallest key value not yet in MST, as shown in execution_table steps 2-4 selecting edges with minimum weights.

Why does the algorithm stop when all nodes are included?

Because MST must connect all nodes without cycles. When mstSet is true for all nodes (see variable_tracker final), MST is complete.

Visual Quiz - 3 Questions

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

A 1-3 (6)

B 0-2 (3)

C 0-1 (2)

D 2-3 (∞)

💡 Hint

Check the 'Edge Selected (u-v)' column at Step 3 in execution_table.

At which step does the node 2 get included in the MST?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at 'Current MST Nodes' column in execution_table to see when node 2 appears.

If the edge 0-2 had weight 1 instead of 3, how would the key array change after Step 2?

A [0,2,3,6]

B [0,1,3,∞]

C [0,2,1,∞]

D [0,∞,∞,∞]

💡 Hint

Refer to 'Updated Keys' column in execution_table and how keys update with smaller edge weights.

Concept Snapshot

Prim's Algorithm for MST:
- Start from any node, add it to MST
- Update keys for adjacent nodes not in MST
- Pick node with smallest key to add next
- Repeat until all nodes included
- MST connects all nodes with minimum total edge weight

Full Transcript

Prim's algorithm builds a minimum spanning tree by starting from any node and adding the closest node not yet in the tree. It keeps track of the minimum edge weights to nodes outside the MST using a key array. At each step, it selects the node with the smallest key value and adds it to the MST set. The parent array records the MST structure. The algorithm stops when all nodes are included. The execution table shows step-by-step how nodes are added, keys updated, and edges selected. The variable tracker shows changes in parent, key, and mstSet arrays. Key moments clarify why keys update only for nodes outside MST, how the next node is chosen, and why the algorithm stops when all nodes are included. The visual quiz tests understanding of edge selection, node inclusion steps, and key updates with changed weights.

Practice

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

easy

A. To sort the vertices of a graph

B. To find the minimum spanning tree of a connected weighted graph

C. To detect cycles in a graph

D. To find the shortest path between two nodes

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 problems

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

3. Final Answer:

   To find the minimum spanning tree of a connected weighted graph -> Option B

4. Quick Check:

   Prim's algorithm = Minimum Spanning Tree [OK]

Hint: Prim's always builds a tree with minimum total edge weight [OK]

Common Mistakes:

• Confusing Prim's with shortest path algorithms
• Thinking it detects cycles
• Assuming it sorts vertices

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

easy

A. int key[V]; for(int i=0; i

B. int key[V] = {0};

C. int key[V] = {INT_MAX};

D. int key[V] = NULL;

Solution

1. Step 1: Understand key array purpose

   The key array stores minimum edge weights to include vertices; initially set to a very large value (infinity).

2. Step 2: Check initialization methods

   int key[V]; for(int i=0; i

3. Final Answer:

   int key[V]; for(int i=0; i -> Option A

4. Quick Check:

   Initialize keys to INT_MAX using loop [OK]

Hint: Use a loop to set all keys to INT_MAX, not zero [OK]

Common Mistakes:

• Initializing key array with zeros
• Using incorrect array initialization syntax
• Assigning NULL to an int array

3. Consider the following adjacency matrix for a graph with 4 vertices:

int graph[4][4] = {
  {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 total weight of the minimum spanning tree?

medium

A. 14

B. 9

C. 11

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. Step 3: Re-evaluate chosen edges for MST

   Actually, the MST edges are 0-1 (2), 1-2 (3), and 1-3 (8) or 0-3 (6) but 0-3 (6) is better than 1-3 (8). So edges are 0-1 (2), 1-2 (3), 0-3 (6) totaling 11.

4. Step 4: Check if a smaller total weight is possible

   Check edges: 0-1 (2), 1-2 (3), 1-3 (8) sum to 13; 0-1 (2), 1-2 (3), 3-4 (not present); so 11 is correct.

5. Final Answer:

   11 -> Option C

6. Quick Check:

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

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

Common Mistakes:

• Including edges that form cycles
• Adding edges with zero weight incorrectly
• Starting from wrong vertex

4. The following code snippet is part of Prim's algorithm implementation. Identify the error:

for (int count = 0; count < V - 1; count++) {
  int u = minKey(key, mstSet);
  mstSet[u] = true;
  for (int v = 0; v < V; v++) {
    if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v])
      key[v] = graph[u][v];
  }
}

medium

A. The loop should run from 1 to V instead of 0 to V-1

B. mstSet[u] should be set to false instead of true

C. The key array is not updated correctly inside the inner loop

D. The condition 'graph[u][v]' should be 'graph[u][v] != 0'

Solution

1. Step 1: Analyze the condition 'graph[u][v]'

   In C, non-zero values are true, zero is false. Using 'graph[u][v]' works but is less clear; better to explicitly check 'graph[u][v] != 0'.

2. Step 2: Check other parts for correctness

   Loop range and key update logic are correct; mstSet[u] should be true to mark visited.

3. Final Answer:

   The condition 'graph[u][v]' should be 'graph[u][v] != 0' -> Option D

4. Quick Check:

   Explicit non-zero check improves clarity [OK]

Hint: Use explicit '!= 0' for clarity in conditions [OK]

Common Mistakes:

• Misunderstanding loop ranges
• Incorrectly toggling mstSet flags
• Not updating key array properly

5. Given a graph with vertices and edges as below:

Vertices: 5
Edges:
0 - 1 (2)
0 - 3 (6)
1 - 2 (3)
1 - 3 (8)
1 - 4 (5)
2 - 4 (7)
3 - 4 (9)

If Prim's algorithm starts from vertex 0, which edges will be included in the minimum spanning tree?

hard

A. Edges: 0-1, 1-2, 1-4, 0-3

B. Edges: 0-1, 1-3, 3-4, 2-4

C. Edges: 0-3, 3-4, 1-4, 1-2

D. Edges: 0-1, 1-2, 2-4, 3-4

Solution

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

   Choose 0-1 (2), then from {0,1} choose 1-2 (3), then 1-4 (5), finally 0-3 (6).

2. Step 2: Confirm no cycles and all vertices included

   All vertices 0,1,2,3,4 are connected with minimum total weight edges without cycles.

3. Final Answer:

   Edges: 0-1, 1-2, 1-4, 0-3 -> Option A

4. Quick Check:

   Pick smallest edges connecting new vertices [OK]

Hint: Always pick smallest edge connecting visited to unvisited vertices [OK]

Common Mistakes:

• Choosing edges with larger weights first
• Including edges that create cycles
• Missing to connect all vertices