Minimum Spanning Tree Prim's Algorithm in DSA C - Build from Scratch

Minimum Spanning Tree using Prim's Algorithm

📖 Scenario: You are working as a network engineer. You need to connect several computers with cables. To save money, you want to use the least total cable length possible while still connecting all computers.This problem can be solved by finding a Minimum Spanning Tree (MST) of the network graph using Prim's Algorithm.

🎯 Goal: Build a program in C that uses Prim's Algorithm to find the Minimum Spanning Tree of a given weighted graph. The program will output the edges chosen and the total minimum cost.

📋 What You'll Learn

Create a 2D array called graph representing the weighted adjacency matrix of the network with 5 nodes.

Create an integer variable num_nodes set to 5.

Create an integer array selected to track nodes included in MST.

Implement Prim's Algorithm using a loop and conditionals to select edges with minimum weight.

Print the edges included in the MST and the total minimum cost.

💡 Why This Matters

🌍 Real World

Network engineers use MST algorithms like Prim's to design cost-efficient networks connecting computers or routers with minimum cable length.

💼 Career

Understanding MST and Prim's Algorithm is important for roles in network design, optimization, and software development involving graph algorithms.

1

Create the graph data structure

Create a 2D integer array called graph with 5 rows and 5 columns representing the weighted adjacency matrix below:

graph = {
{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}
}

Also create an integer variable num_nodes and set it to 5.

DSA C

// Create the graph adjacency matrix and number of nodes
// Your code here

Hint

Use a 2D array with exact values as shown. Also declare num_nodes as 5.

2

Create the selected array to track MST nodes

Create an integer array called selected with size num_nodes and initialize all elements to 0. This array will track which nodes are included in the MST.

DSA C

int graph[5][5] = {
    {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}
};
int num_nodes = 5;

// Create the selected array and initialize to 0
// Your code here

Hint

Declare selected as an integer array of size 5 and initialize all elements to 0.

3

Implement Prim's Algorithm core logic

Write code to implement Prim's Algorithm:
- Start by selecting the first node by setting selected[0] = 1.
- Use a loop that runs num_nodes - 1 times.
- Inside the loop, find the minimum weight edge connecting a selected node to an unselected node.
- Mark the new node as selected.
- Keep track of the edges chosen and the total cost.

Use variables edge_count initialized to 0 and total_cost initialized to 0.

DSA C

int graph[5][5] = {
    {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}
};
int num_nodes = 5;

int selected[5] = {0, 0, 0, 0, 0};

// Implement Prim's Algorithm core logic below
// Your code here

Hint

Use nested loops to find the minimum edge connecting selected and unselected nodes. Update selected, total_cost, and edge_count accordingly.

4

Print the total minimum cost

Add a print statement to display the total minimum cost of the MST using printf with the exact text:
Total minimum cost: %d\n where %d is replaced by total_cost.

DSA C

int graph[5][5] = {
    {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}
};
int num_nodes = 5;

int selected[5] = {0, 0, 0, 0, 0};

selected[0] = 1;
int edge_count = 0;
int total_cost = 0;

while (edge_count < num_nodes - 1) {
    int min = 9999;
    int x = 0;
    int y = 0;

    for (int i = 0; i < num_nodes; i++) {
        if (selected[i]) {
            for (int j = 0; j < num_nodes; j++) {
                if (!selected[j] && graph[i][j]) {
                    if (graph[i][j] < min) {
                        min = graph[i][j];
                        x = i;
                        y = j;
                    }
                }
            }
        }
    }

    printf("Edge %d: %d - %d with weight %d\n", edge_count + 1, x, y, min);
    total_cost += min;
    selected[y] = 1;
    edge_count++;
}

// Print the total minimum cost
// Your code here

Hint

Use printf("Total minimum cost: %d\n", total_cost); to print the final cost.

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