# Prim's Algorithm: Explanation, Code, and Applications

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

## 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 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 treevoid 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 Codeint 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.