Prim's Algorithm for Minimum Spanning Tree: Detailed Explanation and C Implementation

Finding the Minimum Spanning Tree (MST) of a graph is one of the most fundamental problems in graph theory. Prim’s Algorithm is a popular method for solving this problem. Its greedy nature and wide applicability make it a go-to choice for minimizing the cost of connecting nodes in networks.

In this detailed guide, we’ll explore every aspect of Prim’s Algorithm, from its working principles to real-world applications, complete with an implementation in C programming.

Introduction to Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) is a subgraph of a connected, undirected graph that connects all vertices together with the minimum possible total edge weight and without forming cycles.

Key Properties of an MST

The graph must be connected and weighted.
The MST contains V−1V-1 edges for VV vertices.
The MST is unique if all edge weights are distinct.

Applications of MST

MSTs find utility in various domains, such as:

Network Design: Minimizing the cost of constructing roads, electrical grids, or telecommunication networks.
Clustering Algorithms: Dividing data points into groups based on proximity.
Approximation Algorithms: Formulating solutions for complex problems like the Traveling Salesman Problem (TSP).

Overview of Prim’s Algorithm

What is Prim’s Algorithm?

Prim’s Algorithm is a greedy algorithm used to find the MST of a graph. It starts from an arbitrary vertex and grows the tree by adding the smallest edge connecting the tree to a vertex outside the tree.

Greedy Approach

The algorithm ensures that every step minimizes the cost of expanding the MST.

Key Concepts in Prim’s Algorithm

Before diving into the working of Prim’s Algorithm, it’s important to understand some core concepts:

Key Array

This array stores the minimum edge weight required to connect each vertex to the MST.

Parent Array

The parent array helps track the edges included in the MST by storing the parent vertex for each vertex.

MST Set

A boolean array that keeps track of the vertices included in the MST.

Working of Prim’s Algorithm (Step-by-Step Explanation)

Let’s break down the process of Prim’s Algorithm:

Graph Representation

Consider the following adjacency matrix for a graph with five vertices:

	A	B	C	D	E
A	0	2	0	6	0
B	2	0	3	8	5
C	0	3	0	0	7
D	6	8	0	0	9
E	0	5	7	9	0

Step-by-Step Execution

Initialization
- Start with vertex $A$ .
- Initialize the key array as: $[0, \infty, \infty, \infty, \infty]$ .
- Parent array: $[-1, -1, -1, -1, -1]$ .
- MST set: $[False, False, False, False, False]$ .
First Iteration
- Choose the vertex with the minimum key value $(A)$ .
- Add AA to the MST set: $[True, False, False, False, False]$ .
- Update the key and parent arrays:
  - Key: $[0, 2, \infty, 6, \infty]$ .
  - Parent: $[-1, 0, -1, 0, -1]$ .
Second Iteration
- Choose the vertex with the smallest key value $(B)$ .
- Add BB to the MST set: $[True, True, False, False, False]$ .
- Update the key and parent arrays:
  - Key: $[0, 2, 3, 6, 5]$ .
  - Parent: $[-1, 0, 1, 0, 1]$ .
Subsequent Iterations
- Continue selecting the smallest key vertex and updating the arrays until all vertices are included.

Final MST

The resulting MST edges are:

$A−B(2)$
$B−C(3)$
$B−E(5)$
$A−D(6)$

Total Weight: $16$ .

Pseudocode for Prim’s Algorithm

Here’s the pseudocode for Prim’s Algorithm:

Input: A graph G(V, E) represented as an adjacency matrix.
Output: Minimum Spanning Tree (MST).

1. Initialize:
    - key[] = {infinity, ..., infinity}; key[0] = 0
    - parent[] = {-1, ..., -1}
    - mstSet[] = {False, ..., False}
2. For all vertices:
    a. Pick vertex u with the smallest key value from key[] and not in mstSet[].
    b. Include u in mstSet[].
    c. For all adjacent vertices v of u:
        i. If graph[u][v] is non-zero and v is not in mstSet[]:
            Update key[v] and parent[v] if graph[u][v] < key[v].
3. Return the MST edges stored in parent[].

Implementation of Prim’s Algorithm in C

Here’s a complete implementation of Prim’s Algorithm in C:

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

#define INF INT_MAX
#define V 5 // Number of vertices

// Function to find the vertex with the minimum key value
int minKey(int key[], int mstSet[]) {
    int min = INF, minIndex;

    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// Function to print the constructed MST
void printMST(int parent[], int graph[V][V]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
    }
}

// Function to construct and print MST using Prim's Algorithm
void primMST(int graph[V][V]) {
    int parent[V];  // Array to store constructed MST
    int key[V];     // Key values to pick minimum weight edges
    int mstSet[V];  // Boolean array to track vertices in MST

    // Initialize all keys as INF and mstSet[] as false
    for (int i = 0; i < V; i++) {
        key[i] = INF;
        mstSet[i] = 0;
    }

    key[0] = 0;       // Start from the first vertex
    parent[0] = -1;   // First node is the root

    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] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printMST(parent, graph);
}

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;
}

Time and Space Complexity Analysis

Time Complexity

Using Adjacency Matrix: $O(V2)O(V^2)$
Using Min-Heap: $O(Elog⁡V)O(E \log V)$

Space Complexity

$O(V)O(V)$ for $key[], parent[], and mstSet[]$ arrays.

Optimizations in Prim’s Algorithm

While Prim’s Algorithm is efficient for smaller graphs, its basic implementation using an adjacency matrix can be improved for better performance on larger datasets. The key to optimization lies in reducing the time complexity of selecting the minimum key value vertex and updating the adjacent vertices.

Heap-Based Optimization

The most effective optimization replaces the linear search for the minimum key value with a priority queue or a min-heap. This reduces the time complexity from $O(V2)O(V^2)$ to $O(Elog⁡V)O(E \log V)$ , where EE is the number of edges in the graph.

Steps for Optimization

Use a Min-Heap:
- Maintain a priority queue where the keys represent the edge weights, and the vertices are stored as elements.
- Efficiently extract the vertex with the smallest key value.
Dynamic Key Updates:
- Whenever an adjacent vertex’s key is updated, the heap adjusts dynamically.
- This ensures efficient updates to maintain the heap’s properties.

Implementation with Min-Heap

Here’s a high-level implementation of Prim’s Algorithm using a min-heap. While it doesn’t include every detail of heap operations, the main idea is clear:

Pseudocode with Min-Heap

1. Initialize min-heap and insert the starting vertex with a key of 0.
2. While the heap is not empty:
    a. Extract the vertex with the smallest key from the heap.
    b. Include this vertex in the MST set.
    c. For each adjacent vertex:
        i. If the vertex is not in MST and the edge weight is smaller than the key:
            Update the key value.
            Add the vertex to the heap or adjust its position in the heap.
3. Return the MST edges and their total weight.

This implementation significantly speeds up the algorithm, especially for sparse graphs where $E \ll V^2$ .

Applications of Minimum Spanning Trees

Prim’s Algorithm and MSTs, in general, are foundational in several domains. Below are the most common practical applications:

1. Network Design

Telecommunications: Laying out cable networks with minimal cost.
Power Grids: Optimizing the placement of power lines to minimize construction costs.

2. Clustering in Machine Learning

MSTs are used in hierarchical clustering to group data points.
The edges of an MST represent the connections between points, allowing for efficient clustering.

3. Circuit Design

In electronic design, MSTs help minimize the wiring needed between components.

4. Computer Networks

MSTs are used in protocols like Spanning Tree Protocol (STP) to prevent loops in Ethernet networks.

5. Transportation Networks

Designing roadways, railway networks, or pipelines to minimize construction costs.

Frequently Asked Questions

Q1: Can Prim’s Algorithm handle negative edge weights?

Yes, Prim’s Algorithm can handle negative edge weights because it doesn’t rely on edge relaxation like Dijkstra’s Algorithm. The only requirement is that the graph must be connected and undirected.

Q2: How is Prim’s Algorithm different from Kruskal’s Algorithm?

Prim’s Algorithm: Starts from a vertex and grows the MST by adding edges connecting it to the remaining vertices.
Kruskal’s Algorithm: Starts with all edges sorted and adds edges one by one, ensuring no cycles are formed.

Q3: Why is Prim’s Algorithm considered greedy?

It selects the smallest possible edge at each step without considering the global structure, ensuring a locally optimal solution that leads to a globally optimal MST.

Q4: What is the best data structure for implementing Prim’s Algorithm?

A min-heap or priority queue is best for optimizing Prim’s Algorithm, reducing the time complexity to $O(E \log V)$ .

Prim’s Algorithm is a fundamental and widely used algorithm for finding the Minimum Spanning Tree of a graph. Its greedy nature and simplicity make it ideal for numerous real-world applications, from network design to clustering.

In this guide, we explored Prim’s Algorithm in depth, covering:

Its principles and working.
A complete implementation in C programming.
Time complexity analysis and potential optimizations.
Real-world applications that underscore its significance.

Key Takeaways

Prim’s Algorithm is efficient for dense graphs when implemented with an adjacency matrix.
Using a priority queue improves performance, making it suitable for large, sparse graphs.
MSTs are indispensable in optimization problems and network design.

Complete C Code for Reference

Here’s the final, complete implementation of Prim’s Algorithm in C:

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

#define INF INT_MAX
#define V 5 // Number of vertices

// Function to find the vertex with the minimum key value
int minKey(int key[], int mstSet[]) {
    int min = INF, minIndex;

    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// Function to print the constructed MST
void printMST(int parent[], int graph[V][V]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
    }
}

// Function to construct and print MST using Prim's Algorithm
void primMST(int graph[V][V]) {
    int parent[V];  // Array to store constructed MST
    int key[V];     // Key values to pick minimum weight edges
    int mstSet[V];  // Boolean array to track vertices in MST

    // Initialize all keys as INF and mstSet[] as false
    for (int i = 0; i < V; i++) {
        key[i] = INF;
        mstSet[i] = 0;
    }

    key[0] = 0;       // Start from the first vertex
    parent[0] = -1;   // First node is the root

    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] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printMST(parent, graph);
}

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;
}

By mastering Prim’s Algorithm, you’ll gain a deeper understanding of graph theory and optimization, setting a strong foundation for tackling complex computational problems.