In this tutorial we will cover another algorithm which uses greedy approach/technique for finding the solution.
Let's start with a real-life scenario to understant the premise of this algorithm:
Figure 1
Figure 2
The network shown in the second figure basically represents a graph G = (V, E) with a set of vertices V = {a, b, c, d, e, f} and a set of edges E = { (a,b), (b,c), (c,d), (d,e), (e,f), (f,a), (b,f), (c,f) }. The graph is:
A spanning tree G' = (V, E') for the given graph G will include:
E' ⊂ En-1 edges, where n is equal to the total number of edges in GFollowing is an example of a spanning tree for the above graph. Please note that only the highlighted edges are included in the spanning tree,
Figure 3
Also, there can be multiple spanning trees possible for any given graph. For eg: In addition to the spanning tree in the above diagram, the graph can also have another spanning tree as shown below:
Figure 4
By convention, the total number of spanning trees for a given graph can be defined as:
nCm = n!/(m!*(n-m)!), where,
n is equal to the total number of edges in the given graphm is equal to the total number of edges in the spanning tree such that m <= (n-1).Hence, the total number of spanning trees(S) for the given graph(second diagram from top) can be computed as follows:
The cost of a spanning tree is the total of the weights of all the edges in the tree. For example, the cost of spanning tree in Fig. 3 is (2+4+6+3+2) = 17 units, whereas in Fig. 4 it is (2+3+6+3+2) = 16 units.
Since we can have multiple spanning trees for a graph, each having its own cost value, the objective is to find the spanning tree with minimum cost. This is called a Minimum Spanning Tree(MST).
Note: There can be multiple minimum spanning trees for a graph, if any two edges in the graph have the same weight. However, if each edge has a distinct weight, then there will be only one minimum spanning tree for any given graph.
Given a weighted, undirected and connected graph G, the objective is to find the minimum spanning tree G' for G.
Apart from the Prim's Algorithm for minimum spanning tree, we also have Kruskal's Algorithm for finding minimum spanning tree.
However, this tutorial will only discuss the fundamentals of Prim's Algorithm.
Since this algorithm aims to find the spanning tree with minimum cost, it uses greedy approach for finding the solution.
As part of finding the or creating the minimum spanning tree fram a given graph we will be following these steps:
Input Data will be:
A Cost Adjacency Matrix for out graph G, say cost
Output will be:
A Spanning tree with minimum total cost
Below we have the complete logic, stepwise, which is followed in prim's algorithm:
Step 1: Keep a track of all the vertices that have been visited and added to the spanning tree.
Step 2: Initially the spanning tree is empty.
Step 3: Choose a random vertex, and add it to the spanning tree. This becomes the root node.
Step 4: Add a new vertex, say x, such that
Step 5: Repeat the Step 4, till all the vertices of the graph are added to the spanning tree.
Step 6: Print the total cost of the spanning tree.
Let's try to trace the above algorithm for finding the Minimum Spanning Tree for the graph in Fig. 2:
key[] array for storing the key value(or cost) of every vertex. Initialize this to ∞(infinity) for all the verticesbooleanvisited[] for keeping a track of all the vertices that have been added to the spanning tree. Initially this will be 0 for all the vertices, since the spanning tree is empty.parent[] for keeping track of the parent vertex. Initialize this to -1 for all the vertices.
Figure 5: Initial arrays when tree is empty
Choose any random vertex, say f and set key[f]=0.
Figure 6: Setting key value of root node
Since its key value is minimum and it is not visited, add f to the spanning tree.
Figure 7: Root Node
Also, update the following:
minCost = 0 + key[f] = 0visited[] array will look like:
Figure 8: visited array after adding the root node
Figure 9: key array after adding the root node
Note: There will be no change in the parent[] because f is the root node.
Figure 10: parent array after adding the root node
The arrays key[] and visited[] will be searched for finding the next vertex.
visited[f]==1)visited[c]==0, it will be added to the spanning tree.
Figure 11: Adding vertex c
Again, update the following:
minCost = 0 + key[c] = 0 + 1 = 1visited[] array will look like:
Figure 12: visited array after adding vertex c
parent[] array (f becomes the parent of c):
Figure 13: parent array after adding the root node
key[v] will be updated using the formula:
key[v] = min(key[v], cost[c][v])
Thus the key[] array will become:
Figure 14: key array after adding the root node
Repeat the Step C for the remaining vertices.
minCost=1+2=3
Figure 15: Adding vertex a
Figure 16: Updated arrays after adding vertex a
minCost=3+3=6
Figure 17: Adding vertex b to minimum spanning tree
Figure 18: Updated arrays after adding vertex b
minCost=6+3=9
Figure 19: Adding vertex d
Figure 20: Updated arrays after adding vertex d
minCost=9+2=11
Figure 21: Adding vertex e. This is the final minimum spanning tree
Figure 22: Updated arrays after adding vertex e (final arrays)
Now it's time to write a program in C++ for the finding out minimum spanning tree using prim's algorithm.
#include<iostream>
using namespace std;
// Number of vertices in the graph
const int V=6;
// Function to find the vertex with minimum key value
int min_Key(int key[], bool visited[])
{
int min = 999, min_index; // 999 represents an Infinite value
for (int v = 0; v < V; v++) {
if (visited[v] == false && key[v] < min) {
// vertex should not be visited
min = key[v];
min_index = v;
}
}
return min_index;
}
// Function to print the final MST stored in parent[]
int print_MST(int parent[], int cost[V][V])
{
int minCost=0;
cout<<"Edge \tWeight\n";
for (int i = 1; i< V; i++) {
cout<<parent[i]<<" - "<<i<<" \t"<<cost[i][parent[i]]<<" \n";
minCost+=cost[i][parent[i]];
}
cout<<"Total cost is"<<minCost;
}
// Function to find the MST using adjacency cost matrix representation
void find_MST(int cost[V][V])
{
int parent[V], key[V];
bool visited[V];
// Initialize all the arrays
for (int i = 0; i< V; i++) {
key[i] = 999; // 99 represents an Infinite value
visited[i] = false;
parent[i]=-1;
}
key[0] = 0; // Include first vertex in MST by setting its key vaue to 0.
parent[0] = -1; // First node is always root of MST
// The MST will have maximum V-1 vertices
for (int x = 0; x < V - 1; x++)
{
// Finding the minimum key vertex from the
//set of vertices not yet included in MST
int u = min_Key(key, visited);
visited[u] = true; // Add the minimum key vertex to the MST
// Update key and parent arrays
for (int v = 0; v < V; v++)
{
// cost[u][v] is non zero only for adjacent vertices of u
// visited[v] is false for vertices not yet included in MST
// key[] gets updated only if cost[u][v] is smaller than key[v]
if (cost[u][v]!=0 && visited[v] == false && cost[u][v] < key[v])
{
parent[v] = u;
key[v] = cost[u][v];
}
}
}
// print the final MST
print_MST(parent, cost);
}
// main function
int main()
{
int cost[V][V];
cout<<"Enter the vertices for a graph with 6 vetices";
for (int i=0;i<V;i++)
{
for(int j=0;j<V;j++)
{
cin>>cost[i][j];
}
}
find_MST(cost);
return 0;
}
The input graph is the same as the graph in Fig 2.
Figure 23: Output of the program
Time complexity of the above C++ program is O(V2) since it uses adjacency matrix representation for the input graph. However, using an adjacency list representation, with the help of binary heap, can reduce the complexity of Prim's algorithm to O(ElogV).
Finding an MST is a fundamental problem and has the following real-life applications:
Figure 24: Planar Graph
Figure 25: Cut-Set in a Planar Graph
