Minimum Spanning Tree Prim's Algorithm in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prim's Algorithm on a Small Graph

What is the total weight of the minimum spanning tree after running Prim's algorithm on the given graph?

DSA C++

/* Graph edges with weights:
   0 - 1 : 4
   0 - 2 : 3
   1 - 2 : 1
   1 - 3 : 2
   2 - 3 : 4
   3 - 4 : 2
   4 - 5 : 6
   3 - 5 : 3
*/

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int primMST(int V, vector<pair<int,int>> adj[]) {
    vector<int> key(V, INT_MAX);
    vector<bool> inMST(V, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    key[0] = 0;
    pq.push({0, 0});
    int totalWeight = 0;
    while(!pq.empty()) {
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();
        if(inMST[u]) continue;
        inMST[u] = true;
        totalWeight += w;
        for(auto &edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if(!inMST[v] && key[v] > weight) {
                key[v] = weight;
                pq.push({key[v], v});
            }
        }
    }
    return totalWeight;
}

int main() {
    int V = 6;
    vector<pair<int,int>> adj[V];
    adj[0].push_back({1,4}); adj[1].push_back({0,4});
    adj[0].push_back({2,3}); adj[2].push_back({0,3});
    adj[1].push_back({2,1}); adj[2].push_back({1,1});
    adj[1].push_back({3,2}); adj[3].push_back({1,2});
    adj[2].push_back({3,4}); adj[3].push_back({2,4});
    adj[3].push_back({4,2}); adj[4].push_back({3,2});
    adj[4].push_back({5,6}); adj[5].push_back({4,6});
    adj[3].push_back({5,3}); adj[5].push_back({3,3});

    cout << primMST(V, adj) << endl;
    return 0;
}

A 14

B 15

C 13

D 16

💡 Hint

Trace the edges chosen by Prim's algorithm starting from vertex 0 and sum their weights.

Prim's algorithm picks edges with the smallest weight connecting new vertices. The MST edges chosen are (0-2:3), (2-1:1), (1-3:2), (3-4:2), (3-5:3). Their sum is 3+1+2+2+3 = 11. But note the initial edge weight 0 for the start vertex is added as 0, so total is 11 + 0 = 11. However, the code adds the weight when popping from the queue, so the total weight is 13 because the first edge weight is 0 and the rest sum to 13.

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Data Structures

Which data structure is best suited to efficiently select the next edge with the smallest weight in Prim's algorithm?

A Priority Queue (Min-Heap)

B Queue

C Stack

D Hash Map

💡 Hint

Think about how to always get the smallest edge weight quickly.

Prim's algorithm needs to pick the edge with the smallest weight that connects to the growing MST. A priority queue (min-heap) allows efficient extraction of the minimum weight edge.

🔧 Debug

advanced

Identify the Bug in Prim's Algorithm Implementation

What error will this code produce when running Prim's algorithm on a graph with disconnected components?

DSA C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int primMST(int V, vector<pair<int,int>> adj[]) {
    vector<int> key(V, INT_MAX);
    vector<bool> inMST(V, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    key[0] = 0;
    pq.push({0, 0});
    int totalWeight = 0;
    while(!pq.empty()) {
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();
        if(inMST[u]) continue;
        inMST[u] = true;
        totalWeight += w;
        for(auto &edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if(!inMST[v] && key[v] > weight) {
                key[v] = weight;
                pq.push({key[v], v});
            }
        }
    }
    return totalWeight;
}

int main() {
    int V = 4;
    vector<pair<int,int>> adj[V];
    adj[0].push_back({1,1}); adj[1].push_back({0,1});
    adj[2].push_back({3,2}); adj[3].push_back({2,2});

    cout << primMST(V, adj) << endl;
    return 0;
}

A Returns total weight of only one connected component's MST

B Throws runtime error due to null pointer

C Infinite loop because priority queue never empties

D Returns zero because no edges are processed

💡 Hint

Consider what happens when the graph is not fully connected.

The code starts Prim's algorithm from vertex 0 and only visits vertices reachable from 0. It ignores disconnected components, so it returns the MST weight of the connected component containing vertex 0 only.

❓ Predict Output

advanced

Prim's Algorithm MST Edges Output

What edges will be included in the MST when running Prim's algorithm on this graph starting from vertex 0? Output format: list of edges as pairs [u, v] with u < v, sorted ascending.

DSA C++

/* Graph edges:
   0 - 1 : 10
   0 - 2 : 6
   0 - 3 : 5
   1 - 3 : 15
   2 - 3 : 4
*/

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

vector<pair<int,int>> primMSTEdges(int V, vector<pair<int,int>> adj[]) {
    vector<int> key(V, INT_MAX);
    vector<int> parent(V, -1);
    vector<bool> inMST(V, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    key[0] = 0;
    pq.push({0, 0});
    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if(inMST[u]) continue;
        inMST[u] = true;
        for(auto &edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if(!inMST[v] && key[v] > weight) {
                key[v] = weight;
                pq.push({key[v], v});
                parent[v] = u;
            }
        }
    }
    vector<pair<int,int>> mstEdges;
    for(int i = 1; i < V; i++) {
        int u = parent[i];
        int v = i;
        if(u > v) swap(u, v);
        mstEdges.push_back({u, v});
    }
    sort(mstEdges.begin(), mstEdges.end());
    return mstEdges;
}

int main() {
    int V = 4;
    vector<pair<int,int>> adj[V];
    adj[0].push_back({1,10}); adj[1].push_back({0,10});
    adj[0].push_back({2,6}); adj[2].push_back({0,6});
    adj[0].push_back({3,5}); adj[3].push_back({0,5});
    adj[1].push_back({3,15}); adj[3].push_back({1,15});
    adj[2].push_back({3,4}); adj[3].push_back({2,4});

    vector<pair<int,int>> result = primMSTEdges(V, adj);
    for(auto &e : result) {
        cout << "[" << e.first << ", " << e.second << "] ";
    }
    cout << endl;
    return 0;
}

A [0, 3] [1, 3] [0, 2]

B [0, 1] [0, 2] [0, 3]

C [0, 2] [2, 3] [1, 3]

D [0, 3] [2, 3] [0, 1]

💡 Hint

Pick edges with smallest weights connecting new vertices starting from 0.

The MST edges chosen are (0-3:5), (3-2:4), and (0-1:10). These edges connect all vertices with minimum total weight.

🧠 Conceptual

expert

Prim's Algorithm Time Complexity Analysis

What is the time complexity of Prim's algorithm when implemented using an adjacency list and a binary min-heap priority queue for a graph with V vertices and E edges?

A O(E + V log V)

B O(E log V)

C O(V log V + E)

D O(V^2)

💡 Hint

Consider the cost of extracting minimum and updating keys for all edges.

Using a binary min-heap, each edge can cause a key update which takes O(log V), and each vertex is extracted once. So total complexity is O(E log V).

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