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 printed state of the MST edges after running Prim's algorithm on this graph?

DSA C

/* Graph edges with weights:
   0 - 1 (2)
   0 - 3 (6)
   1 - 2 (3)
   1 - 3 (8)
   1 - 4 (5)
   2 - 4 (7)
   3 - 4 (9)
*/

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

#define V 5

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;
        parent[i] = -1;
    }

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

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        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];
            }
        }
    }

    for (int i = 1; i < V; i++) {
        printf("%d - %d\n", parent[i], i);
    }
}

int main() {
    int graph[V][V] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };

    primMST(graph);
    return 0;
}

A

0 - 1
1 - 4
4 - 2
3 - 0

B

0 - 1
0 - 3
3 - 4
1 - 2

C

0 - 1
1 - 2
0 - 3
1 - 4

D

1 - 0
2 - 1
4 - 1
3 - 0

💡 Hint

Trace the algorithm step by step, always picking the smallest edge connecting the MST to a new vertex.

Prim's algorithm starts from vertex 0, picks edge 0-1 (weight 2), then 1-2 (3), then 1-4 (5), and finally 0-3 (6). These edges form the MST.

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Data Structures

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

A Hash Table

B Priority Queue (Min-Heap)

C Queue

D Stack

💡 Hint

Think about how to quickly get the smallest edge weight at each step.

Prim's algorithm uses a priority queue (min-heap) to pick the edge with the smallest weight connecting the MST to a new vertex efficiently.

🔧 Debug

advanced

Identify the Bug in Prim's Algorithm Implementation

What error will this Prim's algorithm code produce when run?

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], key[V], mstSet[V];
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = 0;
        parent[i] = -1;
    }
    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        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];
            }
        }
    }

    for (int i = 1; i < V; i++) {
        printf("%d - %d\n", parent[i], i);
    }
}

int main() {
    int graph[V][V] = {
        {0, 10, 6, 5},
        {10, 0, 0, 15},
        {6, 0, 0, 4},
        {5, 15, 4, 0}
    };
    primMST(graph);
    return 0;
}

A minKey may return -1 causing invalid array access

B mstSet array is not updated causing infinite loop

C parent array is not initialized causing garbage output

D The graph matrix is not symmetric causing wrong MST

💡 Hint

Check what happens if all vertices in mstSet are 1.

If all vertices are included, minKey returns -1, which is used as an index causing invalid memory access.

🚀 Application

advanced

Applying Prim's Algorithm to a Weighted Graph

Given the weighted graph below, which edges will be included in the MST after running Prim's algorithm starting from vertex 0?

DSA C

/* Graph edges:
   0 - 1 (4)
   0 - 7 (8)
   1 - 7 (11)
   1 - 2 (8)
   7 - 8 (7)
   7 - 6 (1)
   2 - 8 (2)
   8 - 6 (6)
   2 - 3 (7)
   2 - 5 (4)
   6 - 5 (2)
   3 - 5 (14)
   3 - 4 (9)
   5 - 4 (10)
*/

A 0-1, 0-7, 7-6, 6-5, 5-2, 2-8, 2-3, 3-4

B 0-7, 7-8, 8-6, 6-5, 5-2, 2-3, 3-4, 0-1

C 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 6-7, 7-8

D 0-1, 1-7, 7-8, 8-2, 2-5, 5-6, 6-3, 3-4

💡 Hint

Start from vertex 0 and always pick the smallest edge connecting to a new vertex.

Prim's algorithm picks edges with minimum weights connecting new vertices. The MST edges are 0-1(4), 0-7(8), 7-6(1), 6-5(2), 5-2(4), 2-8(2), 2-3(7), and 3-4(9).

❓ Predict Output

expert

Output of Prim's Algorithm on a Disconnected Graph

What will be the output of this Prim's algorithm code when run on a disconnected graph?

DSA C

#include <stdio.h>
#include <limits.h>
#define V 6

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], key[V], mstSet[V];
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = 0;
        parent[i] = -1;
    }
    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        if (u == -1) break;
        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];
            }
        }
    }

    for (int i = 1; i < V; i++) {
        if (key[i] == INT_MAX) {
            printf("%d - %d: No connection\n", parent[i], i);
        } else {
            printf("%d - %d\n", parent[i], i);
        }
    }
}

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

A

0 - 1
1 - 2
-1 - 3: No connection
4 - 5
3 - 4

B

noitcennoc oN :5 - 1-
noitcennoc oN :4 - 1-
noitcennoc oN :3 - 1-
2 - 1
1 - 0

C

-1 - 1
1 - 2
-1 - 4
4 - 5
5 - 3

D

0 - 1
1 - 2
-1 - 3: No connection
-1 - 4: No connection
-1 - 5: No connection

💡 Hint

Prim's algorithm only covers connected components reachable from the start vertex.

Vertices 3, 4, and 5 are disconnected from 0, so their keys remain INT_MAX and print 'No connection'.

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