Problem statement:
We’ll be given an undirected, weighted and connected graph. We have to find the minimum spanning tree using prim’s algorithm.
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;
}
This article tried to discuss Prim’s algorithm using priority_queue in STL. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes