How does Prims Algorithm works?

Last updated on December 19th, 2024 at 03:57 am

This article will explore how does Prims Algorithm works, its pseudocode, implementations in various programming languages, and its time complexity.

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.

The Minimum Spanning Tree for a weighted undirected graph is the spanning tree with minimum total weights. The weight of the 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. How Does Prims Algorithm Work?

To understand how Prim’s Algorithm works, let’s break it down into simple steps:

1. Initialization: Start with any vertex as the initial node in the MST.
2. Edge Selection: Find the smallest edge that connects a vertex in the MST to a vertex outside it.
3. Add to MST: Add the selected edge and the new vertex to the MST.
4. Repeat: Continue this process until all vertices are included in the MST.

This process ensures that the MST is built incrementally while maintaining the minimum total edge weight.

4. Pseudo Code of Prim’s Algorithm

Simplified pseudocode for Prim’s Algorithm:

1. Initialize an empty MST and a priority queue (or min-heap).
2. Choose an arbitrary starting vertex and add its edges to the priority queue.
3. While the priority queue is not empty:
   a. Extract the edge with the smallest weight.
   b. If the edge connects a new vertex (not in MST), add it to the MST.
   c. Add all edges of the new vertex to the priority queue.
4. Repeat until all vertices are included in the MST.

5. Prim’s Algorithm in Different Programming Languages

5.1 Prim’s Algorithm 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;
}

5.2 Prim’s Algorithm 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);
    }
}

5.4 Prim’s Algorithm 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()

6. 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.

7. 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.

8. Prim’s Algorithm Time Complexity

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

The time complexity of Prim’s Algorithm depends on the data structures used:

• Adjacency Matrix: (O(V^2)), where (V) is the number of vertices.
• Adjacency List with Min-Heap: (O(E \log V)), where (E) is the number of edges.

The latter is more efficient for sparse graphs.

9. Difference Between Prim’s and Kruskal’s Algorithm

While both algorithms find the MST, they differ in their approach:

• Prim’s Algorithm: Grows the MST one vertex at a time.
• Kruskal’s Algorithm: Sorts all edges and adds them to the MST in increasing order of weight, ensuring no cycles are formed.

10. Does Prim’s Algorithm Work With Negative Weights?

Yes, Prim’s Algorithm works with negative weights, as long as the graph is connected and undirected. The algorithm only considers the relative weights of edges, so negative values do not affect its correctness.

11. Does Prim’s Algorithm Use Depth First Search?

No, Prim’s Algorithm does not use Depth First Search (DFS). Instead, it relies on a greedy approach and a priority queue to select the smallest edge at each step.

FAQs