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'.