Prim's Algorithm - Minimum Spanning Tree

Prim's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, connected, and undirected graph. It builds the MST one vertex at a time, starting from an arbitrary root vertex.

At each step, it adds the cheapest edge that connects a vertex already in the MST to a vertex not yet in the MST.

Think of it like building a snowball: you start with a single snowflake (the root), and you roll it downhill, picking up the closest snow (cheapest edge) to grow it into a big snowball. You never pick up snow that is far away if there is closer snow available.

Key Properties

• Greedy algorithm (makes the locally optimal choice at each step).
• Works only for connected, undirected, and weighted graphs.
• The MST is unique if all edge weights are distinct.

How Prim's Algorithm Works (Step-by-Step)

Step-by-Step Process

1. Initialize:
   • Pick a starting vertex (any vertex). Mark it as visited.
   • Maintain a set of edges that connect visited vertices to unvisited vertices (this is called the "cut").
2. Find Minimum: Select the edge with the minimum weight from the cut.
3. Add to MST: Add this edge and the new vertex to the MST.
4. Update Cut: Add all edges from the newly added vertex to the cut.
5. Repeat steps 2-4 until all vertices are visited (MST has V-1 edges).

Detailed Example

Consider the following weighted undirected graph:

         (2)
    A -------- B
    | \       / |
    |  (4)  (3) |
    |   \   /   |
   (1)   C     (5)
    |   / \     |
    | (6) (7)   |
    | /     \   |
    D -------- E
         (8)

Vertices: A, B, C, D, E. We start from vertex A.

Step-by-Step Execution

Final MST:

    A --- B
    |     |
    D     C
          |
          E

Total Weight = 1 + 2 + 3 + 5 = 11

Algorithm for Prim's Algorithm

Pseudocode

Prim(Graph G, start):
    Input:  G - Weighted, connected, undirected graph
            start - Starting vertex
    Output: MST represented as parent array

    Step 1: Initialize visited[V] = false
    Step 2: Initialize key[V] = ∞
    Step 3: key[start] = 0
    Step 4: Initialize parent[V] = -1

    Step 5: FOR i = 0 to V-1 DO
    Step 6:     u = vertex with minimum key among unvisited vertices
    Step 7:     visited[u] = true
    Step 8:     FOR each neighbor v of u DO
    Step 9:         IF visited[v] == false AND weight(u,v) < key[v] THEN
    Step 10:            key[v] = weight(u,v)
    Step 11:            parent[v] = u
    Step 12:         END IF
    Step 13:     END FOR
    Step 14: END FOR
    Step 15: RETURN parent

Implementation in C (Adjacency Matrix)

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define V 5  // Number of vertices

// Function to find the vertex with minimum key value
int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
    
    for (int v = 0; v < V; v++) {
        if (mstSet[v] == false && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}

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

// Prim's Algorithm function
void primMST(int graph[V][V]) {
    int parent[V];      // Array to store constructed MST
    int key[V];         // Key values used to pick minimum weight edge
    bool mstSet[V];     // To represent set of vertices included in MST
    
    // Initialize all keys as INFINITE and mstSet as false
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }
    
    // Start with vertex 0
    key[0] = 0;
    parent[0] = -1;     // First node is always root of MST
    
    // The MST will have V-1 edges
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum key vertex from the set of vertices not yet processed
        int u = minKey(key, mstSet);
        mstSet[u] = true;
        
        // Update key and parent for adjacent vertices
        for (int v = 0; v < V; v++) {
            // graph[u][v] is non-zero only for adjacent vertices
            // mstSet[v] is false for vertices not yet included
            // Update the key only if graph[u][v] is smaller than key[v]
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    
    printMST(parent, graph);
}

int main() {
    // Adjacency matrix representation of the graph
    int graph[V][V] = {
        {0, 2, 4, 1, 0},
        {2, 0, 3, 0, 5},
        {4, 3, 0, 6, 7},
        {1, 0, 6, 0, 8},
        {0, 5, 7, 8, 0}
    };
    
    primMST(graph);
    return 0;
}

Output:

Edge            Weight
0 - 3           1
0 - 1           2
1 - 2           3
1 - 4           5
Total MST Weight: 11

Implementation in C (Adjacency List with Heap Optimization)

For sparse graphs, using an adjacency list with a binary heap (priority queue) gives better performance.

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

// Adjacency List Node
typedef struct Node {
    int vertex;
    int weight;
    struct Node* next;
} Node;

// Graph structure
typedef struct Graph {
    int vertices;
    Node** adjLists;
} Graph;

// Min Heap Node
typedef struct HeapNode {
    int vertex;
    int key;
} HeapNode;

// Min Heap
typedef struct MinHeap {
    int size;
    int capacity;
    int* position;      // To track positions for decrease-key
    HeapNode** array;
} MinHeap;

// Create a graph
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = vertices;
    graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

// Add edge (undirected)
void addEdge(Graph* graph, int src, int dest, int weight) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->weight = weight;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->weight = weight;
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// Create a min heap node
HeapNode* createHeapNode(int vertex, int key) {
    HeapNode* heapNode = (HeapNode*)malloc(sizeof(HeapNode));
    heapNode->vertex = vertex;
    heapNode->key = key;
    return heapNode;
}

// Create a min heap
MinHeap* createMinHeap(int capacity) {
    MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
    minHeap->position = (int*)malloc(capacity * sizeof(int));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (HeapNode**)malloc(capacity * sizeof(HeapNode*));
    return minHeap;
}

// Swap two heap nodes
void swapHeapNode(HeapNode** a, HeapNode** b) {
    HeapNode* temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify function for min heap
void heapify(MinHeap* minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    
    if (left < minHeap->size && 
        minHeap->array[left]->key < minHeap->array[smallest]->key) {
        smallest = left;
    }
    
    if (right < minHeap->size && 
        minHeap->array[right]->key < minHeap->array[smallest]->key) {
        smallest = right;
    }
    
    if (smallest != idx) {
        // Update positions
        HeapNode* smallestNode = minHeap->array[smallest];
        HeapNode* idxNode = minHeap->array[idx];
        minHeap->position[smallestNode->vertex] = idx;
        minHeap->position[idxNode->vertex] = smallest;
        
        swapHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        heapify(minHeap, smallest);
    }
}

// Check if heap is empty
bool isEmpty(MinHeap* minHeap) {
    return minHeap->size == 0;
}

// Extract minimum node from heap
HeapNode* extractMin(MinHeap* minHeap) {
    if (isEmpty(minHeap)) {
        return NULL;
    }
    
    HeapNode* root = minHeap->array[0];
    HeapNode* lastNode = minHeap->array[minHeap->size - 1];
    minHeap->array[0] = lastNode;
    minHeap->position[root->vertex] = minHeap->size - 1;
    minHeap->position[lastNode->vertex] = 0;
    
    minHeap->size--;
    heapify(minHeap, 0);
    
    return root;
}

// Decrease key value in heap
void decreaseKey(MinHeap* minHeap, int vertex, int key) {
    int i = minHeap->position[vertex];
    minHeap->array[i]->key = key;
    
    while (i && minHeap->array[i]->key < minHeap->array[(i - 1) / 2]->key) {
        minHeap->position[minHeap->array[i]->vertex] = (i - 1) / 2;
        minHeap->position[minHeap->array[(i - 1) / 2]->vertex] = i;
        swapHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Check if vertex is in min heap
bool isInMinHeap(MinHeap* minHeap, int vertex) {
    return minHeap->position[vertex] < minHeap->size;
}

// Prim's Algorithm using adjacency list and min heap
void primMST(Graph* graph) {
    int V = graph->vertices;
    int parent[V];
    int key[V];
    
    // Initialize keys and parents
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        parent[i] = -1;
    }
    
    // Create min heap
    MinHeap* minHeap = createMinHeap(V);
    
    // Initialize heap with all vertices
    for (int i = 0; i < V; i++) {
        minHeap->array[i] = createHeapNode(i, key[i]);
        minHeap->position[i] = i;
    }
    
    // Start with vertex 0
    key[0] = 0;
    minHeap->array[0]->key = 0;
    minHeap->size = V;
    
    // While heap is not empty
    while (!isEmpty(minHeap)) {
        HeapNode* minNode = extractMin(minHeap);
        int u = minNode->vertex;
        
        // Traverse all neighbors of u
        Node* temp = graph->adjLists[u];
        while (temp != NULL) {
            int v = temp->vertex;
            
            // If v is in heap and weight is less than current key
            if (isInMinHeap(minHeap, v) && temp->weight < key[v]) {
                key[v] = temp->weight;
                parent[v] = u;
                decreaseKey(minHeap, v, key[v]);
            }
            temp = temp->next;
        }
    }
    
    // Print MST
    printf("MST Edges (Prim's Algorithm with Heap):\n");
    printf("Edge \tWeight\n");
    int totalWeight = 0;
    for (int i = 1; i < V; i++) {
        printf("%d - %d \t%d\n", parent[i], i, key[i]);
        totalWeight += key[i];
    }
    printf("Total Weight: %d\n", totalWeight);
}

int main() {
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1, 2);
    addEdge(graph, 0, 2, 4);
    addEdge(graph, 0, 3, 1);
    addEdge(graph, 1, 2, 3);
    addEdge(graph, 1, 4, 5);
    addEdge(graph, 2, 3, 6);
    addEdge(graph, 2, 4, 7);
    addEdge(graph, 3, 4, 8);
    
    primMST(graph);
    return 0;
}

Output:

MST Edges (Prim's Algorithm with Heap):
Edge    Weight
0 - 3   1
0 - 1   2
1 - 2   3
1 - 4   5
Total Weight: 11

Complexity Analysis

Time Complexity

Space Complexity

• O(V) for the auxiliary arrays (key, parent, visited).
• O(V + E) for the adjacency list representation.

Advantages of Prim's Algorithm

1. Efficient for Dense Graphs: The adjacency matrix implementation (O(V²)) is simple and works well when the graph is dense (many edges).
2. Guaranteed Optimal: Being a greedy algorithm, it always produces the minimum spanning tree.
3. Simple Concept: The idea of growing the tree from a single vertex is intuitive.

Disadvantages of Prim's Algorithm

1. Requires Connected Graph: Prim's algorithm only works for connected graphs.
2. Memory Overhead: The heap implementation requires extra memory for the heap and position tracking.
3. Not Suitable for Disconnected Graphs: It cannot find a spanning tree for disconnected graphs.

Prim's vs. Kruskal's: Quick Comparison

Practice Questions

1. Given the following graph, find the MST using Prim's algorithm starting from vertex 0:

    0
   /|\
  1 2 3
 /|\
4 5 6