Critical Review of Prim’s Algorithm

Brief of Prim’s Algorithm

At every single step of the Prim’s Algorithm, a cut (of two sets: one containing vertices that are already included in MST, and the other containing the rest of the vertices) is found and the minimum weight edge from the cut is picked and this particular vertex is included to the MST set- this set contains the already included vertices. A group of edges that connects two sets of vertices in a graph is known as a cut in graph theory, as mentioned above.

The idea behind Prim’s Algorithm

The idea can be put very simply- a spanning tree denotes that all vertices must be connected. Hence the two disjoint subsets of vertices need to be connected to make a Spanning Tree, additional to which they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.

The algorithm can be broken down in the following, procedural manner:

1. To begin with, create a set mstSet that keeps track of vertices that were previously included in MST.
2. Go onto assigning a key value to all vertices in the input graph. Initialize all the key values as infinite. For the first vertex, assign the key value as 0, for it to be picked first.
3. For the period of time during which mstSet doesn’t include all vertices:

a. Pick a vertex ‘u’ which is not there in mstSet and has a minimum key value too

b. Include ‘u’ to mstSet

c. Update the key value of all adjacent vertices to u. In order to update the key values, iterate through all adjacent vertices. If weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v- this would be the case for every adjacent vertex.

*In addition to this, key values enable in picking the minimum weight edge from cut (a partition of the vertices of a graph into two disjoint subsets). Key values are used only for vertices which are not yet included in MST, the key value for these vertices indicate the minimum weight edges, connecting them to the set of vertices included in MST.

Complexity of Prim’s algorithm

Time complexity can be described as the amount of time taken by an algorithm to run in the form of a function of the length of the input. The running time of the prim’s algorithm depends upon using the data structure for the graph and the ordering of edges.

The table underneath can be understood in order to understand the relation between data structure used for minimum edge weight and their corresponding time complexity.

Data structure used for minimum edge weight

Time complexity

Adjacency matrix, linear searching

O(|V|2)

Adjacency list and binary heap

O(|E| log |V|)

Adjacency list and Fibonacci heap

O(|E|+ |V| log |V|)

In order to add the edge with the minimum weight, linear searching of an array of weights will be required, which has a corresponding running time of O(|V|2) .

Further improvements can be made by making the use of implementation of heap, in order to find the minimum weight edges in the inner loop of the algorithm.

*Time complexity of the Prim’s algorithm:

*E = no. of edges, V = no. of vertices

Implementation of Prim’s Algorithm

A boolean array mstSet[] to represent the set of vertices included in MST.

If a value falling under mstSet[v] is true, then the vertex v is included in MST, otherwise it’s not.

Array key [] is used to store key values of all vertices. Another array parent [] is used to store indexes of parent nodes in MST. The parent array is the output array which is then used to show the constructed MST.

Below, the implementation of Prim’s Algorithm is taking place in C++, for Prim’s Minimum. The program addresses the adjacency matrix representation of the graph.

#include <bits/stdc++.h>

using namespace std;

// Number of vertices in the graph

#define V 5

// A utility function to find the vertex with

// minimum key value, from the set of vertices

// not yet included in MST

int minKey(int key[], bool mstSet[])

{

// Initialize min value

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;

}

// A utility function to print the

// constructed MST stored in parent[]

void printMST(int parent[], int graph[V][V])

{

cout<<”Edge \tWeight\n”;

for (int i = 1; i < V; i++)

cout<<parent[i]<<” — “<<i<<” \t”<<graph[i][parent[i]]<<” \n”;

}

// Function to construct and print MST for

// a graph represented using adjacency

// matrix representation

void primMST(int graph[V][V])

{

// Array to store constructed MST

int parent[V];

// Key values used to pick minimum weight edge in cut

int key[V];

// To represent set of vertices included in MST

bool mstSet[V];

// Initialize all keys as INFINITE

for (int i = 0; i < V; i++)

key[i] = INT_MAX, mstSet[i] = false;

// Always include first 1st vertex in MST.

// Make key 0 so that this vertex is picked as first vertex.

key[0] = 0;

parent[0] = -1; // First node is always root of MST

// The MST will have V vertices

for (int count = 0; count < V — 1; count++)

{

// Pick the minimum key vertex from the

// set of vertices not yet included in MST

int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set

mstSet[u] = true;

// Update key value and parent index of

// the adjacent vertices of the picked vertex.

// Consider only those vertices which are not

// yet included in MST

for (int v = 0; v < V; v++)

// graph[u][v] is non zero only for adjacent vertices of m

// mstSet[v] is false for vertices not yet included in MST

// Update the key only if graph[u][v] is smaller than key[v]

if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])

parent[v] = u, key[v] = graph[u][v];

}

// print the constructed MST

printMST(parent, graph);

}

// Driver code

int main()

{

/* Let us create the following graph

2 3

(0) — (1) — (2)

| / \ |

6| 8/ \5 |7

| / \ |

(3) — — — -(4)

9 */

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

// Print the solution

primMST(graph);

return 0;

}

*Code reference taken from: Geeksforgeeks

https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/

Following will be the corresponding output:

Edge Weight

0–1 2

1–2 3

0–3 6

1–4 5

The time complexity of the above program would be: O(V²).

Discussing the advantages and shortcomings of Prim’s algorithm:

One of the prime shortcomings of this algorithm is that the list of edges have to be searched from beginning as new edges get added.

If there are more than one edges having the same weight then all possible spanning trees are required to be found for the final minimal tree.

The advantages include its complexity, which is better than its fellow Kruskal’s algorithm. It is highly helpful in dealing with dense graphs that have a lot of edges.

However, alongside this exists the fact that Prim’s algorithm doesn’t allow much control over the chosen edges when multiple edges with the same weight occur at once.