Prim’s Algorithm

Last updated on July 13th, 2024 at 10:28 am

We will discuss Prim’s Algorithm, pseudo code, Code implementation of Prim’s Algorithm in C, Java, JavaScript, Python, advantages & disadvantages, and time of Prim’s Algorithm.

We will discuss the Bubble Sort Algorithm, pseudo code, Code implementation of bubble sort in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Bubble sort.

1. Minimum Spanning Tree

A Spanning Tree is a sub-graph that connects all the vertices together. A single graph can have multiple spanning trees.

Minimum Spanning Tree for a weighted undirected graph is the spanning tree with minimum total weights. The weight of spanning tree is the addition of the weights of all the edges in the spanning tree.

An Minimum Spanning Tree with N vertices, has N−1 edges for a given graph.

2. What is Prim’s Algorithm?

Prim’s Algorithm is a method to find a minimum spanning tree. In this algorithm, the minimum spanning tree formed should always be connected. Prim’s algorithm is an example of a Greedy approach.

Prim’s Algorithm is used to find the Minimum Spanning Tree (MST) of a connected, undirected graph with weighted edges.

The MST is a subset of the edges that connects all the vertices without any cycles and with the minimum possible total edge weight.

2.1 Properties of Prim’s Algorithm

Prim’s Algorithm has the following properties:

1. Prime’s algorithm always results in a single tree.
2. The tree grows until it covers all the vertices of the graph.
3. At each step, an edge is added to the graph that has minimum weight and is the neighbor to the previous vertices.

2.2 Steps of Prim’s Algorithm

1. Find the minimum weight edge from the graph and mark it.
2. Consider the neighboring edges of the selected edges and mark the minimum weight edge among those edges.
3. Continue this until we cover n-1 edges.
4. The resultant tree is a minimum spanning tree and it should always be connected.

3. Pseudo Code of Prim’s Algorithm

PRIM (G, w, s) 
1. for each u in V(G) 
2. do key(u) <- ∞
3. π(v) <- NIL 
4. key[r] <- 0 
5. Q <- V[G] 
6. while Q != empty 
7. do u <- Extract-Min(Q) 
8. for each v in Adjacent[u] 
9. do if v ∈ Q and w(u,v) < key[u] 
10. then π[v] <- u 
11. key[v] <- w(u,v)

4. Code Implementation of Prim’s Algorithm

4.1 Prim’s Algorithm in C

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

#define V 5  // Number of vertices in the graph

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

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

void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

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

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; 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() {
    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;
}

4.1.1 Explanation of Prim’s Algorithm

1. Define Constants and Functions: We define V as the number of vertices. minKey finds the vertex with the smallest key value not yet included in the MST.
2. Initialization: Arrays key to store the minimum weight edge for each vertex and mstSet to track vertices included in the MST are initialized.
3. Prim’s Algorithm: Initialize the first vertex key as 0, indicating it as the starting point. Iterate over all vertices to construct the MST, update keys and parent indexes of the adjacent vertices of the picked vertex.
4. Output: The MST edges and their weights are printed.

4.2 Prim’s Algorithm in Java

import java.util.*;

class Prim {
    private static final int V = 5;

    int minKey(int key[], Boolean mstSet[]) {
        int min = Integer.MAX_VALUE, min_index = -1;

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

        return min_index;
    }

    void printMST(int parent[], int graph[][]) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++)
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
    }

    void primMST(int graph[][]) {
        int parent[] = new int[V];
        int key[] = new int[V];
        Boolean mstSet[] = new Boolean[V];

        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

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

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

            for (int v = 0; v < V; v++)
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
        }

        printMST(parent, graph);
    }

    public static void main(String[] args) {
        Prim t = new Prim();
        int graph[][] = new int[][] { { 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 } };

        t.primMST(graph);
    }
}

4.3 Prim’s Algorithm in JavaScript

const V = 5;

function minKey(key, mstSet) {
    let min = Number.MAX_VALUE;
    let minIndex = -1;

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

    return minIndex;
}

function printMST(parent, graph) {
    console.log("Edge \tWeight");
    for (let i = 1; i < V; i++)
        console.log(`${parent[i]} - ${i} \t${graph[i][parent[i]]}`);
}

function primMST(graph) {
    let parent = Array(V).fill(-1);
    let key = Array(V).fill(Number.MAX_VALUE);
    let mstSet = Array(V).fill(false);

    key[0] = 0;

    for (let count = 0; count < V - 1; count++) {
        let u = minKey(key, mstSet);
        mstSet[u] = true;

        for (let 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);
}

let 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]
];

primMST(graph);

4.4 Prim’s Algorithm in Python

import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]

    def minKey(self, key, mstSet):
        min = sys.maxsize
        for v in range(self.V):
            if key[v] < min and mstSet[v] == False:
                min = key[v]
                min_index = v
        return min_index

    def printMST(self, parent):
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0
        mstSet = [False] * self.V
        parent[0] = -1

        for cout in range(self.V):
            u = self.minKey(key, mstSet)
            mstSet[u] = True

            for v in range(self.V):
                if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        self.printMST(parent)

g = Graph(5)
g.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]]

g.primMST()

5. Advantages of Prim’s Algorithm

1. Optimal Solution: Prim’s Algorithm always produces an MST.
2. Greedy Approach: It’s easy to understand and implement.
3. Dense Graphs: Works well with dense graphs where the number of edges is high.

6. Disadvantages of Prim’s Algorithm

1. Dense Graphs Preference: Not as efficient for sparse graphs compared to Kruskal’s Algorithm.
2. Implementation Complexity: Implementing the priority queue for efficiency can be complex.
3. Performance: For large graphs, the algorithm can be slow if not implemented with advanced data structures like Fibonacci Heaps.

7. Time Complexity of Prim’s Algorithm

Prim’s Algorithm uses a min-heap data structure and its time complexity is O(VlogV+ElogV).

Maximum edges in tree, E = V−1
Therefore, O(VlogV + (V − 1)logV) = O(2VlogV − logV)
Thus, Complexity = O(VlogV)

FAQs