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.