Minimum Spanning Tree Prim's Algorithm in DSA C

Mental Model

Prim's algorithm grows a tree by adding the cheapest edge that connects a new node to the tree until all nodes are included.

Analogy: Imagine building a road network connecting cities. You start from one city and always pick the shortest road to a city not yet connected, gradually linking all cities with minimum total road length.

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

Initial tree:
[1] (start node)
Other nodes: 2, 3, 4

Dry Run Walkthrough

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

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

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

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

Why: We begin from node 1 and look at edges from it to find the cheapest connection.

Step 2: Pick edge (1-2) with weight 2, add node 2 to MST.

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

Why: Edge (1-2) is the cheapest from MST to outside nodes, so add node 2.

Step 3: Pick edge (2-3) with weight 1, add node 3 to MST.

MST nodes: 1 -> 2 -> [3]
Edges considered: (3-4:5), (2-4:4), (1-3:3 but 3 already in MST)

Why: Edge (2-3) is now the cheapest edge connecting MST to outside nodes.

Step 4: Pick edge (2-4) with weight 4, add node 4 to MST.

MST nodes: 1 -> 2 -> 3 -> [4]
All nodes included, MST complete.

Why: Edge (2-4) is the cheapest edge connecting MST to the last outside node.

Result:

Minimum Spanning Tree edges:
1 --2-- 2
2 --1-- 3
2 --4-- 4
Total weight = 7

Annotated Code

DSA C

#include <stdio.h>
#include <limits.h>

#define V 4

int minKey(int key[], int mstSet[]) {
    int min = INT_MAX, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (mstSet[v] == 0 && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}

void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    int mstSet[V];

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = 0;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        if (u == -1) {
            break; // No more reachable vertices
        }
        mstSet[u] = 1;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printf("Edge \tWeight\n");
    int total_weight = 0;
    for (int i = 1; i < V; i++) {
        if (parent[i] != -1) {
            printf("%d - %d \t%d\n", parent[i] + 1, i + 1, graph[i][parent[i]]);
            total_weight += graph[i][parent[i]];
        }
    }
    printf("Total weight = %d\n", total_weight);
}

int main() {
    int graph[V][V] = {
        {0, 2, 3, 0},
        {2, 0, 1, 4},
        {3, 1, 0, 5},
        {0, 4, 5, 0}
    };

    primMST(graph);
    return 0;
}

int u = minKey(key, mstSet);

Select the next node with the smallest key value not yet in MST

mstSet[u] = 1;

Add selected node to MST set

if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {

Update key and parent if edge offers cheaper connection to MST

parent[v] = u;

Record the MST connection for node v

key[v] = graph[u][v];

Update minimum edge weight to node v

Output

Edge 	Weight

1 - 2 	2

2 - 3 	1

2 - 4 	4

Total weight = 7

Complexity Analysis

Time: O(V^2) because we scan all vertices to find the minimum key in each iteration and update keys for all adjacent vertices.

Space: O(V) for arrays storing keys, parents, and MST set membership.

vs Alternative: Compared to Kruskal's algorithm which sorts edges O(E log E), Prim's is better for dense graphs with adjacency matrix representation.

Edge Cases

Graph with single node

Algorithm returns immediately with no edges in MST.

DSA C

for (int count = 0; count < V - 1; count++) {

Disconnected graph

Algorithm only builds MST for connected component containing start node; other nodes remain unreachable.

DSA C

int u = minKey(key, mstSet); // returns -1 if no reachable node

Graph with equal edge weights

Algorithm picks edges in order of node indices when weights tie, still producing a valid MST.

DSA C

if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {

When to Use This Pattern

When you need to connect all points with minimum total cost and the graph is dense or given as adjacency matrix, reach for Prim's algorithm because it grows the MST by adding the cheapest edge from the tree to a new node.

Common Mistakes

Mistake: Not updating the key array when a cheaper edge is found.
Fix: Always update key[v] when a smaller edge weight is found connecting v to MST.

Mistake: Including nodes multiple times by not marking them in mstSet.
Fix: Mark nodes as included in MST immediately after selecting them.

Summary

Prim's algorithm builds a minimum spanning tree by adding the cheapest edge connecting a new node to the growing tree.

Use it when you want to connect all nodes with minimum total edge weight, especially in dense graphs.

The key insight is to keep track of the cheapest edge to each node outside the MST and pick the smallest one each step.

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