Prim’s Algorithm

Before starting Prim’s algorithm I’d like to briefly discuss about spanning tree.

Spanning Tree

Spanning tree is a subset of a graph which has all the vertices covered with minimum possible number of edges. A spanning tree cannot be disconnected. Also, a spanning tree cannot have any loops (or cycles).

If n = number of vertices,

Number of edges of a spanning tree = n-1

Total number of spanning trees possible = n^(n-2)

Figure 1: Possible spanning trees from Graph G

In Figure 1,

Nodes/vertices(n) = 3,

Number of edges of spanning tree= n-1 = 2,

Total possible spanning trees = n^(n-2) = 3^(3–2) = 3

Minimum Spanning Tree(MST)

A minimum spanning tree is a spanning tree with the minimum possible weight from all the possible spanning trees. More than one minimum spanning trees can exist with the same weight.

Let’s discuss this more with an example.

Figure 2: Cost of some possible spanning trees from Graph G

In Figure 2, there are some of the possible spanning trees from the graph. Here , you can see that different spanning trees have different weights.
The MST of the given graph is 5 units, and those MSTs are Spanning Tree 1, 3 and 5.

Greedy Algorithm

Greedy algorithm is the approach of solving a problem by breaking the problem into smaller problems, then solving it by selecting the best possible approach of the smaller problem, and finally combining those pieces together to solve the bigger problem eventually.

Prim’s Algorithm

Prim’s algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) for a weighted undirected graph.
Prim’s starts with a single source node and keeps on repeatedly exploring the adjacent nodes of the source node to find the shortest weight possible.

Steps of finding MST using Prim’s Algorithm —

1. Define a new tree with a single node which can be any node from the graph.
2. Connect the vertex to another adjacent vertex, but some things must be considered:
   a. Among all the possible adjacent vertices, the one with the minimum weight must be selected as the next node.
   b. A cycle or loop must never be formed.
3. Repeat step 2 until all the nodes from the trees are selected.

Weight of the minimum spanning tree equals to sum of weights of all the edges.

Understanding Prim’s Algorithm with an example —

Figure 3 has a weighted undirected graph. Let’s find its MST using Prim’s algorithm.

Figure 3: Weighted undirected graph used in the example

Now, as per the algorithm,

Let’s select a vertex, which can be any vertex from the graph(step 1). Let’s take vertex B for this example, as shown in figure 4.

Figure 4

Now, we need to check for adjacent vertex as shown in figure 5.

Figure 5

Now, we need to select the minimum weight of BD or BC.
Here, weight of BD = 4 units, weight of BC = 10 units. So, we’ll choose BD as it has the least weight.
Now, we have B and D in our tree. Figure 6 shows how the graph will look after performing these steps.

Figure 6

We’ll check adjacent nodes of B and D now, keeping in mind that no loops or cycles should be formed. From figure 6, we can see that there are three possible edges we can select. They are BC, DC and DE with weight 10, 2 and 1 respectively. We’ll select the one with the least weight, i.e. DE with weight 1.

Now, we have B, C and E as vertex in the tree and we’ll look for adjacent nodes from each of them.

Figure 7 shows the graph we’ll have after performing these steps.

Figure 7

Now, from figure 7 we can see that nodes B, D and E are all connected to C. There are 3 ways to connect those via BC, DC and EC. Again we’ll choose the least weight available, so, we’ll go with DC as the edge.

The result will look like what’s shown in Figure 8.

Figure 8

Now, we have B, D, E and C vertices in our graph. Only vertex A is left. There’s only one connected with A, i.e. CA. So, we’ll choose that edge as the last edge.

Now, we have the final result(MST) with us. It’s shown in Figure 9.

This method of finding MST is called Prim’s Algorithm.

Figure 9

Now, let’s calculate the weight of this minimum spanning tree.

Weight of BD = 4 units,
Weight of DE = 1 units,
Weight of CD = 2 units,
Weight of CA = 3 units

Weight of minimum spanning tree = Sum of all the weights
So, Weight of MST = 4 + 1 + 2 + 3 = 10 units

Figure 10: All the steps are shown visually

Implementation of Prim’s Algorithm(in C++) —

Taken from GeeksforGeeks
Link

// A C++ program for Prim’s Minimum
// Spanning Tree (MST) algorithm. The program is
// for 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;
}

Output:

Edge   Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5

Time complexity of Prim’s Algorithm —

Time complexity of Prim’s algorithm using the above program is O(V²).

But, the time complexity of Prim’s algorithm can be further reduced. If we use adjacency list for input of the graph, and binary heap, then the time complexity of Prim’s algorithm will get reduced to O(|E|log|V|).