Prim's Algorithm: Explanation, Code, and Applications

Board Infinity -

Introduction

Prim's Algorithm turns a given graph into a tree with the least possible sum of its edges. It is known as a Minimum Spanning Tree. In order to discover this least-spanning tree, it employs the greedy method. The chosen data structure affects how long the algorithm takes to run.

  • The article provides a detailed explanation of Prim's algorithm as well as an algorithm walkthrough.
  • We go over the method's code and talk about how long various C++ implementations of the algorithm take.
  • The justification additionally included The algorithm's adjacency matrix implementation

Implementation

Prims Algorithm is a Greedy Algorithm meaning that at every step, the algorithm will make a decision depending on what is the best choice at that point.

It provides the best solution for the immediate issue and makes the assumption that the greatest solution will ultimately be found for the entire issue.

Steps:

  1. Pick a random vertex on the graph to begin with, then mark it as visited.
  2. Choose the least-weighted edge that has not yet been processed after iterating through all the visited vertices.
  3. Step 2 should be repeated until all nodes have been visited.

Code:

#include <bits/stdc++.h>
using namespace std;
#define V 5

int findMaxVertex(bool visited[], int weights[])
{
    // Stores the index of max-weight vertex from set of unvisited vertices
    int index = -1;
    // Stores the maximum weight from the set of unvisited vertices
    int maxW = INT_MIN;

    for (int i = 0; i < V; i++) {
        // If the current node is unvisited and weight of current vertex is greater than maxW
        if (visited[i] == false
            && weights[i] > maxW) {
            // Update maxW
            maxW = weights[i];
            // Update index
            index = i;
        }
    }
    return index;
}

void printMaximumSpanningTree(int graph[V][V], int parent[])
{
    // Stores total weight of maximum spanning tree of a graph
    int MST = 0;
    // Iterate over all possible nodes of a graph
    for (int i = 1; i < V; i++) {
        // Update MST
        MST += graph[i][parent[i]];
    }
    cout << "Weight of the maximum Spanning-tree "
         << MST << '\n'
         << '\n';
    cout << "Edges \tWeight\n";
    // Print the Edges and weight of maximum spanning tree of a graph
    for (int i = 1; i < V; i++) {
        cout << parent[i] << " - " << i << " \t"
             << graph[i][parent[i]] << " \n";
    }
}
// Function to find the maximum spanning tree
void maximumSpanningTree(int graph[V][V])
{
    // visited[i]:Check if vertex i is visited or not
    bool visited[V];
    // weights[i]: Stores maximum weight of  graph to connect an edge with
    int weights[V];
    // parent[i]: Stores the parent node of vertex i
    int parent[V];
    // Initialize weights as -INFINITE, and visited of a node as false
    for (int i = 0; i < V; i++) {
        visited[i] = false;
        weights[i] = INT_MIN;
    }
    // Include 1st vertex in maximum spanning tree
    weights[0] = INT_MAX;
    parent[0] = -1;
 
    for (int i = 0; i < V - 1; i++) {
        int maxVertexIndex = findMaxVertex(visited, weights);
        // Mark that vertex as visited
        visited[maxVertexIndex] = true;
        // Update adjacent vertices of the current visited vertex
        for (int j = 0; j < V; j++) {
            // If there is an edge between j and current visited vertex and
            // also j is unvisited vertex
            if (graph[j][maxVertexIndex] != 0
                && visited[j] == false) {
                // If graph[v][x] is greater than weight[v]
                if (graph[j][maxVertexIndex] > weights[j]) {
                    // Update weights[j]
                    weights[j] = graph[j][maxVertexIndex];
                    // Update parent[j]
                    parent[j] = maxVertexIndex;
                }
            }
        }
    }
    // Print maximum spanning tree
    printMaximumSpanningTree(graph, parent);
}
// Driver Code
int main()
{
    // Given graph
    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 } };
    // Function call
    maximumSpanningTree(graph);
    return 0;
}

write your code here: Coding Playground

Time Complexity

The adjacency matrix implementation utilizes a nested for loop in findMST() that iterates from 0 to V. Therefore, the time complexity is O(V^2). Can be minimized depending on the data structure.

The time it takes to choose a vertex with minimum weight at each step will be reduced if the input graph's vertices are stored in a binary heap and organized by weight.

Applications

  1. Maze generation: The prim's approach can be used to create a maze for a weighted graph random in nature. The exit and entry nodes for the maze might be any two nodes.
  2. Cable laying, electric grids layout, and LAN networks, especially in cases where the graphs are dense: Can be achieved by connecting all the nodes while checking that the least amount of cable is being used for any situation. Hence optimizing.