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

Prim's algorithm builds the MST by starting from one node, adding the closest node not yet in the MST, and repeating until all nodes are included.

Execution Sample

DSA C++

vector<vector<pair<int,int>>> graph = {
  {{1,2}, {3,6}},
  {{0,2}, {2,3}, {3,8}, {4,5}},
  {{1,3}, {4,7}},
  {{0,6}, {1,8}, {4,9}},
  {{1,5}, {2,7}, {3,9}}
};

// Prim's MST starting at node 0

This code defines the weighted graph in C++ using adjacency list and illustrates Prim's algorithm starting from node 0 to find the minimum spanning tree.

Execution Table

Step	Operation	Nodes in MST	Edges Considered	Selected Edge	MST Visual State
1	Start at node 0	[0]	Edges: (0-1:2), (0-3:6)	None	0
2	Select min edge from MST to non-MST	[0,1]	(0-1:2), (0-3:6)	(0-1:2)	0 --2-- 1
3	Select min edge from MST to non-MST	[0,1,2]	(1-2:3), (1-3:8), (1-4:5), (0-3:6)	(1-2:3)	0 --2-- 1 --3-- 2
4	Select min edge from MST to non-MST	[0,1,2,4]	(2-4:7), (1-3:8), (1-4:5), (0-3:6)	(1-4:5)	0 --2-- 1 --3-- 2 | 5 4
5	Select min edge from MST to non-MST	[0,1,2,4,3]	(4-3:9), (1-3:8), (0-3:6)	(0-3:6)	3 --6-- 0 --2-- 1 --3-- 2 | 5 4
6	All nodes included	[0,1,2,4,3]	None	None	MST complete: 0-1-2-4-3

💡 All nodes are included in MST, algorithm stops.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
MST Nodes	[0]	[0,1]	[0,1,2]	[0,1,2,4]	[0,1,2,4,3]	[0,1,2,4,3]
Edges Considered	[(0-1:2),(0-3:6)]	[(1-2:3),(1-3:8),(1-4:5),(0-3:6)]	[(2-4:7),(1-3:8),(1-4:5),(0-3:6)]	[(4-3:9),(1-3:8),(0-3:6)]	[]	[]
Selected Edge	None	(0-1:2)	(1-2:3)	(1-4:5)	(0-3:6)	None

Key Moments - 3 Insights

Why do we start Prim's algorithm from any node and still get the same MST weight?

Prim's algorithm grows the MST by always choosing the smallest edge connecting MST to non-MST nodes (see steps 2-5). Starting node only changes order, not final MST weight.

Why do we update edges considered after adding a new node to MST?

After adding a node, new edges from this node to non-MST nodes become candidates (see 'Edges Considered' column in steps 3-5). This ensures we always pick the smallest connecting edge.

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

Once all nodes are in MST (step 6), no edges connect MST to outside nodes, so the MST is complete and the algorithm stops.

Visual Quiz - 3 Questions

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

A (1-4:5)

B (0-3:6)

C (2-4:7)

D (1-3:8)

💡 Hint

Check the 'Selected Edge' column at step 4 in the execution table.

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

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

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

If the edge (0-3) had weight 1 instead of 6, how would the selected edge at step 2 change?

A (0-1:2)

B (0-3:1)

C (1-2:3)

D No change

💡 Hint

At step 2, the algorithm picks the minimum edge from MST to non-MST nodes.

Concept Snapshot

Prim's Algorithm for MST:
- Start from any node
- Add closest node not in MST
- Update edges connecting MST to outside
- Repeat until all nodes included
- Always pick minimum weight edge connecting MST to non-MST

Full Transcript

Prim's algorithm builds a minimum spanning tree by starting from any node and repeatedly adding the closest node not yet in the MST. At each step, it updates the edges connecting the MST to nodes outside it and selects the edge with the smallest weight. This process continues until all nodes are included in the MST. The execution table shows the nodes included, edges considered, and the selected edge at each step. The variable tracker records the MST nodes and edges considered after each step. Key moments clarify why the starting node does not affect the MST weight, why edges are updated, and why the algorithm stops when all nodes are included. The visual quiz tests understanding of edge selection and MST growth steps.

Practice

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

easy

A. To find the shortest path between two nodes

B. To detect cycles in a graph

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

D. To sort the vertices of a 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 minimum total edge weight.

2. Step 2: Differentiate from other graph algorithms

   It is not used for shortest path, cycle detection, or sorting vertices, which are different problems.

3. Final Answer:

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

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 nodes

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]; for(int i=0; i

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

Solution

1. Step 1: Understand key array role

   The key array stores minimum edge weights to include each vertex; initially, all are set to a very large value (infinity).

2. Step 2: Check initialization options

   Setting key[i] = INT_MAX correctly represents infinity; other options set to 0 or -1 are incorrect for this purpose.

3. Final Answer:

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

4. Quick Check:

   Initialize keys with INT_MAX for minimum edge tracking [OK]

Hint: Initialize keys with INT_MAX to represent infinity [OK]

Common Mistakes:

• Initializing keys with 0 instead of INT_MAX
• Using negative values incorrectly
• Not initializing keys at all

3. Consider the following graph with 4 vertices and edges with weights:

0 - 1 : 10
0 - 2 : 6
0 - 3 : 5
1 - 3 : 15
2 - 3 : 4

What is the total weight of the minimum spanning tree found by Prim's Algorithm starting from vertex 0?

medium

A. 21

B. 19

C. 20

D. 25

Solution

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

   Edges from 0: (0-3)=5, (0-2)=6, (0-1)=10. Pick (0-3)=5 first.

2. Step 2: Add next minimum edge connecting new vertices

   From vertices {0,3}, edges are (3-2)=4, (3-1)=15, (0-2)=6, (0-1)=10. Pick (3-2)=4 next.

3. Step 3: Add last vertex with minimum edge

   From {0,3,2}, edges to 1 are (0-1)=10 and (3-1)=15. Pick (0-1)=10.

4. Step 4: Calculate total weight

   Total = 5 + 4 + 10 = 19.

5. Final Answer:

   19 -> Option B

6. Quick Check:

   Sum of chosen edges = 19 [OK]

Hint: Pick smallest edge connecting new vertex each step [OK]

Common Mistakes:

• Choosing edges with larger weights first
• Not updating the set of included vertices
• Adding edges that form cycles

4. The following C++ code snippet is intended to implement Prim's Algorithm but has a bug. What is the error?

const int V = 4;
int key[V] = {INT_MAX, INT_MAX, INT_MAX, INT_MAX};
bool mstSet[V] = {false, false, false, false};
key[0] = 0;
for (int count = 0; count < V - 1; count++) {
    int u = -1;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && (u == -1 || key[v] < key[u]))
            u = v;
    }
    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 condition 'graph[u][v]' should check for non-zero edges

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

C. The key array is not initialized with INT_MAX

D. The variable 'u' is initialized incorrectly inside the loop

Solution

1. Step 1: Analyze the neighbor update condition

   The condition if(graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) uses graph[u][v] as a boolean check (true if non-zero).

2. Step 2: Identify the bug

   This implicit check assumes positive weights and treats 0 as no edge. Standard implementations explicitly use graph[u][v] != 0 to clearly indicate checking for edge existence (non-zero weight).

3. Step 3: Rule out other options

   A: 'u' is correctly initialized to -1 inside each iteration. B: V-1 iterations build the tree correctly. C: key array is initialized with INT_MAX.

4. Final Answer:

   The condition 'graph[u][v]' should check for non-zero edges -> Option A

5. Quick Check:

   Edge check: graph[u][v] != 0 [OK]

Hint: Check edge existence condition carefully for zero weights [OK]

Common Mistakes:

• Misinitializing 'u' outside the loop
• Incorrect loop range
• Not initializing key array properly

5. Given a graph with vertices 0 to 5 and edges:

0-1: 3, 0-3: 1, 1-2: 1, 1-3: 3, 1-4: 10, 2-4: 5, 3-4: 6, 4-5: 2

If Prim's Algorithm starts from vertex 0, which edge will NOT be included in the minimum spanning tree?

hard

A. Edge 1-2 with weight 1

B. Edge 0-1 with weight 3

C. Edge 4-5 with weight 2

D. Edge 3-4 with weight 6

Solution

1. Step 1: Build MST step-by-step from vertex 0

   Start at 0: edges (0-3)=1, (0-1)=3. Pick (0-3)=1 first.

2. Step 2: Add next minimum edges connecting new vertices

   From {0,3}, edges: (3-1)=3, (3-4)=6, (0-1)=3. Pick (0-1)=3 or (3-1)=3 (same weight). Pick (0-1)=3.

3. Step 3: Continue adding minimum edges

   From {0,1,3}, edges: (1-2)=1, (1-4)=10, (3-4)=6. Pick (1-2)=1.

4. Step 4: Add edge to vertex 4

   From {0,1,2,3}, edges: (2-4)=5, (3-4)=6, (1-4)=10. Pick (2-4)=5.

5. Step 5: Add edge to vertex 5

   From {0,1,2,3,4}, edge: (4-5)=2.

6. Step 6: Identify excluded edge

   Edge (3-4)=6 is not chosen because (2-4)=5 is cheaper and connects 4 earlier.

7. Final Answer:

   Edge 3-4 with weight 6 -> Option D

8. Quick Check:

   Exclude heavier edge when cheaper path exists [OK]

Hint: Always pick smallest edge connecting new vertex, exclude heavier alternatives [OK]

Common Mistakes:

• Including heavier edges when cheaper ones exist
• Not updating candidate edges after each addition
• Assuming all edges connected to MST are included