Last Updated on January 30, 2024 by Ankit Kochar
Embarking on the journey of understanding Prim’s algorithm and its implementation using the priority_queue in the C++ Standard Template Library (STL) opens a gateway to the realm of efficient minimum spanning tree algorithms. Prim’s algorithm is renowned for its simplicity and effectiveness in finding the minimum spanning tree of a connected, undirected graph. This article delves into the intricacies of Prim’s algorithm and demonstrates its application using the priority_queue data structure in the STL. We’ll be given an undirected, weighted and connected graph. We have to find the minimum spanning tree using prim’s algorithm. Let’s unravel the concepts, explore the implementation, and understand how this algorithm optimally connects the dots in graph theory.
What is Prim’s Algorithm?
Prim’s algorithm is a greedy algorithm. Prim’s algorithm is used to find the minimum spanning tree. It finds the subset of edges that includes every vertex such that the sum of the weights of the edges can be minimized.
How does Prim’s algorithm work?
First, we’ll initialize the MST with a random vertex then we’ll find the tree that connects the tree with the new vertices.
Then select the minimum edge and add it to the tree. Then repeat the previous step until a minimum spanning tree is found.
Applications of prim’s algorithm:
- It is used in network designing.
- It is used in electrical cables.
- Also can be used in network cycles.
We’ll implement our own priority queue. In CPP STL provides priority queue but it doesn’t support decrease key operation.
In prim’s algorithm, we need a priority queue and some operations such as:
- Extract_min: All the vertices which are not included in the minimum spanning tree, we need to get the minimum key value vertex.
- Decrease_key: After extracting the vertex we need to update the keys which are its adjacent vertices and if the value of the new key is smaller, then we’ll update it.
Algorithm:
- Initialize all the keys as infinite and mark the parent of every vertex as -1.
- Create an empty priority_queue q.
- Every item of p is a pair of weight, vertex.
- Then initialize all the vertices as not part of the minimum spanning tree (for this we’ll use bool array).
- Insert a source vertex into p and mark its key as 0.
- Then, extract the minimum key vertex and mark that vertex as x.
- Mark x as true.
- Traverse all the adjacent vertices and repeat the steps.
Dry Run
Consider the graph shown below.
Let us say that we want to construct the minimum spanning tree for this graph. So, let us take an empty priority queue as shown below.
So, we have a boolean array visited which shows that initially, no vertex is visited and we have a priority queue that is empty. Initially, let us insert the vertex 0 and the weight here will also be 0.
Now, as per the algorithm, we remove it from the priority queue, mark it visited in the boolean array, and insert its neighbors in the priority queue.
So, as shown above, we have removed vertex 0, marked it true in the visited array, and inserted the neighboring vertices 1 and 3 with their respective edge weights.
Now, the lower cost edge weight will be considered by the priority queue. So, vertex 1 will be removed now and its neighbor vertex 2 with weight 10 will be inserted.
Also, the spanning tree is shown by shading the edges (look at the image below).
Now, vertex 2 will be removed and vertex 3 will be inserted with a cost of 10.
Now, the vertex 3 will be removed but the one with the cost 10. Also, vertex 4 will be inserted.
Now, vertex 4 will be removed and vertex 5 with the weight 3 and vertex 6 with the weight 8 will be added.
Now, vertex 5 will be removed and vertex 6 with weight 3 will be added.
Finally, vertex 6 with weight 3 will be removed.
So, we finally get the minimum spanning tree.
#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
typedef pair<int, int> iPair;
class Graph
{
int V;
list< pair<int, int> > *adj;
public:
Graph(int V);
void addEdge(int u, int v, int w);
void primMST();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<iPair> [V];
}
void Graph::addEdge(int u, int v, int w)
{
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
void Graph::primMST()
{
priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
int src = 0;
vector<int> key(V, INF);
vector<int> parent(V, -1);
vector<bool> inMST(V, false);
pq.push(make_pair(0, src));
key[src] = 0;
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if(inMST[u] == true){
continue;
}
inMST[u] = true;
list< pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = (*i).first;
int weight = (*i).second;
if (inMST[v] == false && key[v] > weight)
{
key[v] = weight;
pq.push(make_pair(key[v], v));
parent[v] = u;
}
}
}
for (int i = 1; i < V; ++i)
printf("%d - %d\n", parent[i], i);
}
int main()
{
int V = 9;
Graph g(V);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
g.primMST();
return 0;
}
Time complexity : O(E log V).
Faster Implementation using an array of vectors represented as a weighted graph.
#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
typedef pair<int, int> iPair;
void addEdge(vector <pair<int, int> > adj[], int u,
int v, int wt)
{
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}
void primMST(vector<pair<int,int> > adj[], int V)
{
priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
int src = 0;
vector<int> key(V, INF);
vector<int> parent(V, -1);
vector<bool> inMST(V, false);
pq.push(make_pair(0, src));
key[src] = 0;
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if(inMST[u] == true){
continue;
}
inMST[u] = true;
for (auto x : adj[u])
{
int v = x.first;
int weight = x.second;
if (inMST[v] == false && key[v] > weight)
{
key[v] = weight;
pq.push(make_pair(key[v], v));
parent[v] = u;
}
}
}
for (int i = 1; i < V; ++i)
printf("%d - %d\n", parent[i], i);
}
int main()
{
int V = 9;
vector<iPair > adj[V];
addEdge(adj, 0, 1, 4);
addEdge(adj, 0, 7, 8);
addEdge(adj, 1, 2, 8);
addEdge(adj, 1, 7, 11);
addEdge(adj, 2, 3, 7);
addEdge(adj, 2, 8, 2);
addEdge(adj, 2, 5, 4);
addEdge(adj, 3, 4, 9);
addEdge(adj, 3, 5, 14);
addEdge(adj, 4, 5, 10);
addEdge(adj, 5, 6, 2);
addEdge(adj, 6, 7, 1);
addEdge(adj, 6, 8, 6);
addEdge(adj, 7, 8, 7);
primMST(adj, V);
return 0;
}
Conclusion
In conclusion, Prim’s algorithm, when implemented with the aid of the priority_queue in the C++ Standard Template Library, emerges as a powerful tool for finding minimum spanning trees in connected, undirected graphs. Its simplicity, combined with the efficiency of the priority_queue, makes it a valuable asset in network design, ensuring optimal connectivity with minimal edge weights. As we navigate the intricacies of this algorithm, we gain insights into its applications and the elegance with which it addresses graph theory problems, solidifying its place as a cornerstone in the realm of computer science algorithms.
FAQs Related to Prim’s Algorithm using Priority Queue
Here are some FAQs related to Prim’s Algorithm.
1. What is Prim’s algorithm, and what is its significance in graph theory?
Prim’s algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph. Its significance lies in its ability to efficiently connect all the vertices of the graph with the minimum possible total edge weight, making it a key tool in network design and optimization.
2. How does Prim’s algorithm work?
Prim’s algorithm starts with an arbitrary node and systematically adds the shortest edge connecting any explored node to an unexplored one. This process continues until all nodes are included, forming the minimum spanning tree. The algorithm always selects the shortest available edge at each step, ensuring the minimization of the total edge weight.
3. What is the role of a priority queue in Prim’s algorithm implementation?
A priority queue is used to efficiently retrieve the minimum-weight edge at each step of the algorithm. The priority_queue in the STL allows the algorithm to prioritize edges based on their weights, facilitating a streamlined selection process and contributing to the overall efficiency of Prim’s algorithm.
4. How is the priority_queue structured in Prim’s algorithm implementation?
The priority_queue is structured in a way that the edge with the minimum weight is always at the front. This ensures that when an edge is selected for inclusion in the minimum spanning tree, it is the one with the smallest weight, adhering to the greedy nature of Prim’s algorithm.
5. Can Prim’s algorithm handle graphs with weighted edges and disconnected components?
Prim’s algorithm is designed for connected graphs. In the case of disconnected components, the algorithm can be applied separately to each connected component to find the minimum spanning tree for each subgraph.
6. How does Prim’s algorithm compare to other minimum spanning tree algorithms, like Kruskal’s algorithm?
Prim’s algorithm and Kruskal’s algorithm both find minimum spanning trees, but they differ in their approaches. Prim’s is a greedy algorithm that starts from a single vertex and grows the tree, while Kruskal’s is based on sorting all edges and adding them one by one while avoiding cycles. The choice between them often depends on the characteristics of the graph.
7. Are there any scenarios where Prim’s algorithm might not be the optimal choice?
Prim’s algorithm is well-suited for dense graphs with many edges. However, in sparse graphs where the number of edges is significantly smaller than the total possible edges, other algorithms like Kruskal’s might be more efficient. The choice of algorithm depends on the specific characteristics of the graph in question.