C Programming: Prim's Algorithm

Welcome to this comprehensive guide on C Programming's Prim's Algorithm! This tutorial is designed to be beginner-friendly, yet packed with enough detail to cater to intermediate learners as well. Let's dive right in!

Introduction 🎯

Prim's Algorithm is a popular algorithm used in graph theory to find the minimum spanning tree (MST) of a graph. In this tutorial, we'll understand the concept, workings, and implementation of Prim's Algorithm in C.

Prerequisites 📝

Before we dive into Prim's Algorithm, let's ensure you have a good grasp of the following concepts:

Basic C Programming (variables, loops, functions, arrays)
Data Structures (specifically, arrays and linked lists)

Minimum Spanning Tree (MST) 💡

A Minimum Spanning Tree (MST) is a tree that spans all the vertices of a graph and has the minimum possible total edge weight. MSTs are useful in various applications such as network design, transportation, and computer networks.

The Prim's Algorithm 📝

Prim's Algorithm works by gradually building the MST by adding vertices (nodes) one-by-one, starting from an arbitrary vertex. It does this by finding the minimum weight edge that connects the current MST with an unvisited vertex and adding that edge to the MST.

Algorithm Steps 💡

Start at an arbitrary vertex and add it to the MST.
For each unvisited vertex, find the minimum weight edge connecting it to the MST.
Add the vertex along with the minimum weight edge to the MST.
Repeat steps 2 and 3 until all vertices are in the MST.

Implementation in C 🎯

Let's implement Prim's Algorithm in C using an adjacency matrix representation of the graph.

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

void minHeapify(int v, int n, int parent[], int key[], int heap[][V]) {
    int smallest = v;
    int left = 2 * v + 1;
    int right = 2 * v + 2;

    if (left < n && heap[left][key[left]] < heap[smallest][key[smallest]])
        smallest = left;

    if (right < n && heap[right][key[right]] < heap[smallest][key[smallest]])
        smallest = right;

    if (smallest != v) {
        int temp_key = heap[v][key[v]];
        int temp_heap = heap[v][smallest];
        heap[v][smallest] = temp_heap;
        heap[smallest][v] = temp_key;

        int temp_parent = parent[v];
        parent[v] = parent[smallest];
        parent[smallest] = temp_parent;

        minHeapify(smallest, n, parent, key, heap);
    }
}

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

    int key[V] = {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX};
    int parent[V] = {-1, -1, -1, -1, -1, -1, -1, -1, -1};
    int mst_set[V] = {0};

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

    int heap[V][2] = {{src, key[src]}, {-1, -1}};

    while (n > 1) {
        int u = heap[0][0];
        minHeapify(u, n, parent, key, heap);
        n--;

        int min = INT_MAX;
        int min_index;

        for (int v = 0; v < V; v++) {
            if (mst_set[v] == 0 && graph[u][v] && key[v] > graph[u][v]) {
                parent[v] = u;
                key[v] = graph[u][v];
                mst_set[v] = 1;
                min = graph[u][v];
                min_index = v;
            }
        }

        if (min != INT_MAX) {
            heap[n][0] = min_index;
            heap[n][1] = key[min_index];
        }
    }

    printf("Edges in the Minimum Spanning Tree:\n");
    for (int i = 1; i < V; ++i) {
        printf("%d - %d, Weight: %d\n", parent[i] + 1, i + 1, key[i]);
    }

    return 0;
}

💡 Pro Tip: This implementation uses a min-heap to efficiently find the minimum weight edge connecting the current MST with an unvisited vertex.

Quiz 🎯

This concludes our in-depth exploration of Prim's Algorithm in C Programming. Happy coding! 🎉