Minimum Spanning Tree:
A graph that doesn’t have directions is called an undirected graph. Every graph must have a path from one node to another node. A spanning tree is also an undirected connected graph where all the nodes of the graph are present with minimum edges. If a spanning tree doesn’t have all the nodes of the graph, then we cannot say that it is a spanning tree. The spanning-tree total weights will be less than the original weight of the graph as we connected it through the minimum weight edges. The spanning-tree also does not have a cycle. Any graph has more than one spanning tree, but only one of those will be unique. We call it a minimal spanning tree since we’re attempting to create a full graph with all nodes while keeping the weight low.
We can draw a spanning tree with the help of the following two methods:
- Kruskal’s algorithm
- Prim’s algorithm
In this article, we are going to discuss Prim’s algorithm. Kruskal’s algorithm will be discussed in the next article.
Prim’s Algorithm:
Prim’s algorithm is used to find the minimum spanning tree of a graph. The prim’s algorithm starts from any node and then adds any adjacent node whose weight is the minimum, and this process continues till all the nodes in the graphs are visited. When creating the minimum spanning tree of a graph, we also have to do not create any cycles because cycles should not be in the minimum spanning tree.
Prim’s Algorithm Steps:
The prim’s algorithm employs the greedy approach for the minimum spanning tree. We have to choose any vertex of the graph and then choose the next adjacency vertex whose weight is less, and we continue this process till we do not get the whole graph nodes connected.
Step 1: Choose any source vertex in the graph.
Step 2: Find the minimum weight edge that is adjacent to the source and then connect it to the spanning tree.
Step 3: Repeat step 2 until all nodes are not added into the minimum spanning tree.
Example :
The below is an example to search a minimum spanning tree using Prim’s algorithm.
1. We choose any random node from graph G and add it to the MST (minimum spanning tree). We select here node 0.
2. Now, we select that edge that is adjacent to the source node (0) but with the smallest weight, and then add that smallest weight node to the minimum spanning tree.
3. Now, we select that edge that is adjacent to the source node (0 or 1) but with the smallest weight, and then add that smallest weight node to the minimum spanning tree.
4. Now, we select that edge that is adjacent to the source node (0, 1, or 3) but with the smallest weight, and then add that smallest weight node to the minimum spanning tree.
5. Now, we select that edge that is adjacent to the source node (0, 1, 3, or 4) but with the smallest weight, and then add that smallest weight node to the minimum spanning tree.
6. Now, we select that edge that is adjacent to the source node (0, 1, 3, 4, or 6) but with the smallest weight, and then add that smallest weight node to the minimum spanning tree.
7. Now, we select that edge that is adjacent to the source node (0, 1, 3, 4, 6, or 2) but with the smallest weight, and then add that smallest weight node to the minimum spanning tree.
Above is our final MST (minimum spanning tree), and the total cost is 6.
C++ Prim’s MST (Minimum Spanning Tree) Program:
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
typedef std :: pair<int,int> SII;
typedef std :: vector<SII> SSII;
int PrimsMST (int sourceNode, std :: vector<SSII> & graph){
// This queue will store details of each node
// along with their weight value.
std :: priority_queue<SII, std :: vector<SII>, std :: greater<SII>> k;
k.push(std :: make_pair(0, sourceNode));
bool nodesAdded[graph.size()];
memset(nodesAdded, false, sizeof(bool)*graph.size());
int mst_tree_cost = 0;
while (!k.empty()) {
// We are selecting here the node which has minimum cost
SII itemNode;
itemNode = k.top();
k.pop();
int Node = itemNode.second;
int Cost = itemNode.first;
// Here we are checking if any node has not been added to the MST,
// then adding that node.
if (!nodesAdded[Node]) {
mst_tree_cost += Cost;
nodesAdded[Node] = true;
// Iterate over the negibour nodes which were recently taken
// out of the priority queue.
// and added to the MST which is not yet added
for (auto & pair_node_cost : graph[Node]) {
int adjency_node = pair_node_cost.second;
if (nodesAdded[adjency_node] == false) {
k.push(pair_node_cost);
}
}
}
}
return mst_tree_cost;
}
int main(){
// The details of the graph with cost and adjency node.
SSII fromNode_0_in_graph_1 = { {1,1}, {2,2}, {1,3},
{1,4}, {2,5}, {1,6} };
SSII fromNode_1_in_graph_1 = { {1,0}, {2,2}, {2,6} };
SSII fromNode_2_in_graph_1 = { {2,0}, {2,1}, {1,3} };
SSII fromNode_3_in_graph_1 = { {1,0}, {1,2}, {2,4} };
SSII fromNode_4_in_graph_1 = { {1,0}, {2,3}, {2,5} };
SSII fromNode_5_in_graph_1 = { {2,0}, {2,4}, {1,6} };
SSII fromNode_6_in_graph_1 = { {1,0}, {2,2}, {1,5} };
int num_of_nodes = 7; // Total Nodes (0 to 6)
std :: vector<SSII> primsgraph;
primsgraph.resize(num_of_nodes);
primsgraph[0] = fromNode_0_in_graph_1;
primsgraph[1] = fromNode_1_in_graph_1;
primsgraph[2] = fromNode_2_in_graph_1;
primsgraph[3] = fromNode_3_in_graph_1;
primsgraph[4] = fromNode_4_in_graph_1;
primsgraph[5] = fromNode_5_in_graph_1;
primsgraph[6] = fromNode_6_in_graph_1;
// As we already know, we have to choose the source vertex,
// so we start from the vertex 0 node.
std :: cout << "Total cost of minimum spanning tree after Prim's algorithm : "
"" << PrimsMST(0, primsgraph) << std :: endl;
return 0;
}
Output:
Time Complexity of Prim’s MST Algorithm:
1. The total time required to process and select the specific priority queue node that has yet to be added to the MST is logV.But as it works for every vertex, the total time complexity is V (logV).
2. The graph is undirected, and the total edges will be 2E. As we have to push the nodes into the priority queue, it will take a total time log (V). However, because we have a total of 2E edges, our total push operation will be 2E (log (V)).
3. Total complexity after operation 1 and 2 is O( ( E + V ) log ( V )).
Conclusion:
We have studied the Prim’s minimum spanning tree, which is the first preference of most people when they have to find the MST graph from a graph. The Prim’s algorithm is simple to grasp and implement in a real-world application.Prim’s algorithm is very useful in real-life applications, for example, connecting railway tracks to whole over the cities. So it’s just a single example, but its application is huge, so we must have to understand this algorithm.
