DSA-II | DSA-II Lab | Python | TOC | Data Analytics-Lab | Networking | NET/SET | Data Science

Prim's Algorithm

Minimum Spanning Tree

          A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is also a tree (connected and acyclic). In simpler terms, it’s a way to connect all the points in your graph without any loops, using the fewest possible edges. If your graph is weighted, a minimum spanning tree is a spanning tree with the smallest possible total edge weight. For better understanding of minimum spanning tree and Prim’s Algorithm watch this video.

Prim's Algorithm

Watching this video, you might you under the way Prim’s algorithm work. Also refer this algorithm.

  1. Initialize two disjoint sets:

    • Set A: Contains vertices already included in the MST.

    • Set B: Contains vertices not yet included in the MST.

  2. Initialize a priority queue (min-heap):

    • The priority queue stores edges in the form (weight, u, v), where u is a vertex in set A, v is a vertex in set B, and weight is the weight of the edge connecting them.

  3. Steps:

    • Start with an arbitrary vertex (e.g., vertex 0) and add it to set A.

    • Add all edges connected to this vertex to the priority queue.

    • While set B is not empty:

      • Extract the edge with the minimum weight from the priority queue. Let this edge be (weight, u, v).

      • If v is in set B:

        • Add v to set A.

        • Add (u, v) to the MST.

        • Add all edges connected to v (that lead to vertices in set B) to the priority queue.

      • Else, discard the edge (since v is already in set A).

  4. Termination:

    • The algorithm terminates when set B is empty, meaning all vertices are included in the MST.

The result is a minimum spanning tree for the graph

Prim's Algorithm and Greedy Strategy

                  Prim’s algorithm uses a greedy strategy to find the minimum spanning tree. “Greedy” means that at each step, the algorithm makes the locally optimal choice without considering the overall, long-term consequences. In Prim’s algorithm, this translates to always picking the edge with the smallest weight that connects a vertex already in the spanning tree to a vertex not yet included.

Here’s how the greedy strategy plays out in Prim’s algorithm:

  1. Local Optimization: At each iteration, the algorithm only considers the edges connected to the vertices currently in the spanning tree. It selects the edge with the minimum weight among these, regardless of how this choice might affect future edge selections. This is a purely local decision.
  2. No Backtracking: Once an edge is added to the spanning tree, it’s never removed. The algorithm doesn’t reconsider previous choices, even if they later turn out to be suboptimal in the context of the entire tree. This lack of backtracking is a hallmark of greedy algorithms.
  3. Global Optimality: While each step is locally optimal, the greedy strategy, in the case of Prim’s algorithm, remarkably leads to a globally optimal solution, i.e., a minimum spanning tree. This isn’t always the case with greedy algorithms; for many other problems, greedy approaches only find approximate solutions.

It’s important to note that the greedy strategy doesn’t guarantee the absolute minimum spanning tree in cases where multiple minimum spanning trees exist with the same total weight. Prim’s algorithm will find one of these minimum spanning trees, but not necessarily all of them.

 Assignment 5. Set A b) SPPU:

Writing a C Program  for the implementation of Prims Algorithm.
download code
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100
#define INF INT_MAX

// Structure to represent an edge in the graph
struct Edge {
    int u, v, weight;
};

// Structure to represent a min-heap node
struct MinHeapNode {
    int vertex, key;
};

// Structure to represent a min-heap
struct MinHeap {
    int size, capacity;
    int* pos; // To store the position of each vertex in the heap
    struct MinHeapNode** array;
};

// Function to create a new min-heap node
struct MinHeapNode* newMinHeapNode(int vertex, int key) {
    struct MinHeapNode* node = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
    node->vertex = vertex;
    node->key = key;
    return node;
}

// Function to create a min-heap
struct MinHeap* createMinHeap(int capacity) {
    struct MinHeap* heap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    heap->size = 0;
    heap->capacity = capacity;
    heap->pos = (int*)malloc(capacity * sizeof(int));
    heap->array = (struct MinHeapNode**)malloc(capacity * sizeof(struct MinHeapNode*));
    return heap;
}

// Function to swap two min-heap nodes
void swapMinHeapNodes(struct MinHeapNode** a, struct MinHeapNode** b) {
    struct MinHeapNode* temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify at a given index
void minHeapify(struct MinHeap* heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->array[left]->key < heap->array[smallest]->key) {
        smallest = left;
    }
    if (right < heap->size && heap->array[right]->key < heap->array[smallest]->key) {
        smallest = right;
    }
    if (smallest != idx) {
        struct MinHeapNode* smallestNode = heap->array[smallest];
        struct MinHeapNode* idxNode = heap->array[idx];

        // Swap positions
        heap->pos[smallestNode->vertex] = idx;
        heap->pos[idxNode->vertex] = smallest;

        // Swap nodes
        swapMinHeapNodes(&heap->array[smallest], &heap->array[idx]);
        minHeapify(heap, smallest);
    }
}

// Function to check if the heap is empty
int isEmpty(struct MinHeap* heap) {
    return heap->size == 0;
}

// Function to extract the minimum node from the heap
struct MinHeapNode* extractMin(struct MinHeap* heap) {
    if (isEmpty(heap)) {
        return NULL;
    }

    struct MinHeapNode* root = heap->array[0];
    struct MinHeapNode* lastNode = heap->array[heap->size - 1];

    // Move the last node to the root
    heap->array[0] = lastNode;

    // Update positions
    heap->pos[root->vertex] = heap->size - 1;
    heap->pos[lastNode->vertex] = 0;

    // Reduce heap size and heapify the root
    heap->size--;
    minHeapify(heap, 0);

    return root;
}

// Function to decrease the key value of a vertex
void decreaseKey(struct MinHeap* heap, int vertex, int key) {
    int i = heap->pos[vertex];
    heap->array[i]->key = key;

    // Fix the min-heap property
    while (i && heap->array[i]->key < heap->array[(i - 1) / 2]->key) {
        heap->pos[heap->array[i]->vertex] = (i - 1) / 2;
        heap->pos[heap->array[(i - 1) / 2]->vertex] = i;
        swapMinHeapNodes(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Function to check if a vertex is in the min-heap
int isInMinHeap(struct MinHeap* heap, int vertex) {
    return heap->pos[vertex] < heap->size;
}

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

// Function to implement Prim's algorithm
void primMST(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
    int parent[vertices]; // Array to store the MST
    int key[vertices];    // Key values used to pick the minimum weight edge

    // Create a min-heap
    struct MinHeap* heap = createMinHeap(vertices);

    // Initialize the min-heap with all vertices and infinite key values
    for (int v = 1; v < vertices; v++) {
        parent[v] = -1;
        key[v] = INF;
        heap->array[v] = newMinHeapNode(v, key[v]);
        heap->pos[v] = v;
    }

    // Start with vertex 0
    key[0] = 0;
    heap->array[0] = newMinHeapNode(0, key[0]);
    heap->pos[0] = 0;
    heap->size = vertices;

    // Loop until the heap is empty
    while (!isEmpty(heap)) {
        struct MinHeapNode* minNode = extractMin(heap);
        int u = minNode->vertex;

        // Traverse all adjacent vertices of u
        for (int v = 0; v < vertices; v++) {
            if (graph[u][v] && isInMinHeap(heap, v)) { // Fixed the missing parenthesis here
                if (graph[u][v] < key[v]) {
                    key[v] = graph[u][v];
                    parent[v] = u;
                    decreaseKey(heap, v, key[v]);
                }
            }
        }
    }

    // Print the MST
    printMST(parent, graph, vertices);
}

int main() {
    int vertices, edges;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);

    int graph[MAX_VERTICES][MAX_VERTICES] = {0};

    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    printf("Enter the edges (source destination weight):\n");
    for (int i = 0; i < edges; i++) {
        int src, dest, weight;
        scanf("%d %d %d", &src, &dest, &weight);
        graph[src][dest] = weight;
        graph[dest][src] = weight; // Undirected graph
    }

    primMST(graph, vertices);

    return 0;
}
Table of Contents
Kruskal's Algorithm
dijkstra's Agorithm
Piyu's CS

Computer Science Education

Contact Us

info@piyuscs.com