Minimum Spanning Tree Prim's Algorithm in DSA C++

Mental Model

Start from any node and keep adding the cheapest edge that connects a new node to the growing tree until all nodes are included.

Analogy: Imagine building a road network connecting all cities with the least total cost by always choosing the cheapest road that links a new city to the network you already built.

Graph nodes: 0, 1, 2, 3
Edges with weights:
0 --2-- 1
0 --3-- 3
1 --1-- 2
2 --4-- 3

Initial:
0
1
2
3

Start from node 0:
[0]
1
2
3

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: (0-1:2), (0-3:3), (1-2:1), (2-3:4). Start from node 0.

Goal: Build a tree connecting all nodes with minimum total edge weight.

Step 1: Start from node 0, add it to MST set

MST nodes: [0]
Edges considered: (0-1:2), (0-3:3)

Why: We begin from node 0 to start building the MST.

Step 2: Choose edge with smallest weight connecting MST to new node: (0-1:2)

MST nodes: 0 -> [1]
Edges considered: (1-2:1), (0-3:3)

Why: Edge (0-1) has the smallest weight among edges from MST to outside.

Step 3: Choose next smallest edge connecting MST to new node: (1-2:1)

MST nodes: 0 -> 1 -> [2]
Edges considered: (0-3:3), (2-3:4)

Why: Edge (1-2) is the smallest edge connecting MST to a new node.

Step 4: Choose next smallest edge connecting MST to new node: (0-3:3)

MST nodes: 0 -> 1 -> 2 -> [3]
All nodes included

Why: Edge (0-3) is the smallest edge connecting MST to the last node.

Result:

MST edges: (0-1:2), (1-2:1), (0-3:3)
Total weight: 6

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <climits>

using namespace std;

// Graph represented as adjacency list: vector of (neighbor, weight)
class Graph {
public:
    int V;
    vector<vector<pair<int, int>>> adj;

    Graph(int vertices) : V(vertices) {
        adj.resize(V);
    }

    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    void primMST(int start) {
        vector<int> key(V, INT_MAX); // min weight to connect node
        vector<bool> inMST(V, false); // track nodes included in MST
        vector<int> parent(V, -1); // store MST edges

        key[start] = 0;
        // Min-heap: (key, vertex)
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            if (inMST[u]) continue; // skip if already included
            inMST[u] = true; // include node in MST

            for (auto &[v, w] : adj[u]) {
                if (!inMST[v] && w < key[v]) {
                    key[v] = w; // update min edge weight
                    parent[v] = u; // update parent
                    pq.push({key[v], v}); // push updated edge
                }
            }
        }

        // Print MST edges and total weight
        int total_weight = 0;
        for (int i = 0; i < V; i++) {
            if (parent[i] != -1) {
                cout << parent[i] << " - " << i << " : " << key[i] << "\n";
                total_weight += key[i];
            }
        }
        cout << "Total weight: " << total_weight << "\n";
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 3, 3);
    g.addEdge(1, 2, 1);
    g.addEdge(2, 3, 4);

    g.primMST(0);
    return 0;
}

key[start] = 0;

Initialize start node key to 0 to pick it first

pq.push({0, start});

Add start node to priority queue to begin MST

int u = pq.top().second; pq.pop();

Extract node with smallest key not yet in MST

if (inMST[u]) continue; inMST[u] = true;

Skip if already included; else mark node as included

for (auto &[v, w] : adj[u]) { if (!inMST[v] && w < key[v]) { key[v] = w; parent[v] = u; pq.push({key[v], v}); } }

Update keys and parents for neighbors if cheaper edge found

for (int i = 0; i < V; i++) { if (parent[i] != -1) { cout << parent[i] << " - " << i << " : " << key[i] << "\n"; total_weight += key[i]; } }

Print MST edges and accumulate total weight

Output

0 - 1 : 2

1 - 2 : 1

0 - 3 : 3

Total weight: 6

Complexity Analysis

Time: O(E log V) because each edge is processed and priority queue operations take log V time

Space: O(V + E) for adjacency list and auxiliary arrays

vs Alternative: Compared to Kruskal's algorithm which sorts edges first (O(E log E)), Prim's with priority queue is efficient for dense graphs

Edge Cases

Graph with single node

MST is empty with total weight 0

DSA C++

key[start] = 0;

Disconnected graph

Only connected component from start node is included in MST; others remain excluded

DSA C++

if (inMST[u]) continue;

Multiple edges with same weight

Algorithm picks any minimal edge connecting new node; MST remains valid

DSA C++

if (!inMST[v] && w < key[v])

When to Use This Pattern

When you need to connect all points with minimum total cost and the graph is weighted, use Prim's MST to grow the tree step-by-step by always adding the cheapest edge to a new node.

Common Mistakes

Mistake: Not marking nodes as included in MST causing infinite loops
Fix: Set inMST[u] = true immediately after extracting node from priority queue

Mistake: Updating keys without checking if new edge weight is smaller
Fix: Only update key[v] and parent[v] if w < key[v]

Summary

Builds a minimum spanning tree by adding the cheapest edge connecting new nodes to the growing tree.

Use when you want to connect all nodes with minimum total edge weight in a weighted graph.

Always pick the smallest edge connecting the MST to a new node to ensure minimal total cost.

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