Table of Contents
Introduction
Graph algorithms are always quite intimidating to start with but are pretty easy to comprehend if you get the hang of it. We will discuss here one such beautiful algorithm to find the Minimum Spanning tree of a given Graph.
Well before we move forward with the algorithm let me give you a brief introduction of what is a Minimum Spanning Tree.
A spanning tree is a subset of a graph such that it spans every vertex of the graph. Suppose for a graph G (Vertices, Edges), a subset of this graph is considered a Spanning Tree if the subgraph contains all the vertices in the original graph.
When we are asked about Minimum Spanning Tree, this means, the subgraph that we selected not only contains all the vertices of the original graph G but also the sum of the weights of the edges connecting those vertices is also minimum. There can be multiple solutions i.e. multiple Minimum Spanning Trees to a particular graph.
Let me make this clear with an image:
Let our original Graph G be:
Then our Minimum Spanning tree for the graph G can be:
Real-World Application of Minimum Spanning Tree
A Minimum Spanning Tree has multiple real-world applications like:
- The building or Connecting of roads among cities or villages at a minimal cost.
- Network service providers for finding the minimal cost to provide service to every user.
- Cluster Analysis of data sets
- Protocols to avoid network cycles
- Maximum bottleneck paths
- A real-time face tracking algorithm
- Dithering algorithms
- Prime Factorial
There are several algorithms for finding the Minimum Spanning Tree of a given Graph but some of the most popular algorithms are – Kruskal’s Algorithm and Prims Algorithm. In this article, we will comprehensively discuss Prims Algorithm to find the MST of graph G.
Prims Algorithm
Well, the intuition of this algorithm is similar to Dijkstra’s Algorithm, which is a greedy algorithm. The idea is to use min heap (priority queue) to store the vertices and their respective edge weights. Now, in general, we use an adjacency list to efficiently represent a dense graph, hence we will use an adjacency list for the same.
In this method first, we will create a Min heap of size V (number of vertices) and keep it in a pair with its edge weight. We will push the starting node into the priority queue based on weight. Then for every node, we are visiting we will also maintain a visited boolean array to maintain which nodes are visited and which are not.
For every new node that we visit, we will have all the other edges connected to this current node as an active edge. Among these active edges, we choose the edge with minimum weight and add that weight to our answer.
Then we pop out the current node and move to the next node that is connected with the active edge selected.
We repeat this strategy till all the V nodes are visited and by the end, we will have the sum of minimum spanning tree weight.
Let me explain this with a small test case:
Let’s dry run for this graph, we insert the first starting node 1 to the queue and for which we have active edges to 2, 3, and 4. The active edge we select first is 2 or 3. Suppose we select 3. Then we move to the next node 3 and now the active edges are 4 and 2, again we select anyone, let 4, then we are only left with node 2 to be spanned, we traverse to node 2 again from node 1. Now the spanning-tree weight sum becomes 1 + 1 + 2 = 4, that is our answer.
Then the Minimum Spanning Tree becomes
Algorithm
Starting from any source vertex of the graph
- Choose the edge with the smallest weight among all the active edges of any source.
- We need to select the vertex in MST.
- Add the edges starting with the previous vertex in the active edge list.
- Then we repeat the second step again and again till we have all the vertices in our graph.
Code Implementation
C++
#include <bits/stdc++.h>
using namespace std;
class Graph{
vector<pair<int,int>> *l;
int V;
public:
Graph(int n){
V = n;
l = new vector<pair<int,int>> [n];
}
void addEdge(int x,int y,int w){
l[x].push_back({y,w});
l[y].push_back({x,w});
}
int prim_mst(){
//min heap
priority_queue<pair<int,int>, vector<pair<int,int> > ,greater<pair<int,int>>> Q;
//visited array that denotes if a node has been included in MST or not
bool *visited = new bool[V]{0};
int ans = 0;
//start from source node
Q.push({0,0});
while(!Q.empty()){
//pick the edge with min weight
auto best = Q.top();
Q.pop();
int to = best.second;
int weight = best.first;
if(visited[to]){
continue;
}
ans += weight;
visited[to] = 1;
//add new edges
for(auto x:l[to]){
if(visited[x.first] == 0){
Q.push({x.second,x.first});
}
}
}
return ans;
}
};
int main()
{
int n,m;
cin>>n>>m;
Graph g(n);
for(int i = 0;i<m;i++){
int x,y,w;
cin>>x>>y>>w;
g.addEdge(x-1,y-1,w);
}
cout<<g.prim_mst()<<"\n";
return 0;
}
Input: 8 9
1 2 10
2 3 12
2 8 14
2 6 6
3 4 7
4 5 9
5 6 11
6 7 12
7 8 13
Output: 68
Java Implementation (Prims Algorithm in Java)
import java.util.LinkedList;
import java.util.TreeSet;
import java.util.Comparator;
public class prims {
class newnode {
int destination;
int weight;
newnode(int a, int b)
{
destination = a;
weight = b;
}
}
static class Graph {
int V;
LinkedList<newnode>[] adj;
Graph(int edge)
{
V = edge;
adj = new LinkedList[V];
for (int o = 0; o < V; o++)
adj[o] = new LinkedList<>();
}
}
class node {
int vertex;
int key;
}
class comparator implements Comparator<node> {
@Override
public int compare(node originnode, node newnode)
{
return originnode.key - newnode.key;
}
}
void addEdge(Graph graph, int src, int destination, int weight)
{
newnode originnode = new newnode(destination, weight);
newnode node = new newnode(src, weight);
graph.adj[src].addLast(originnode);
graph.adj[destination].addLast(node);
}
void prims_mst(Graph graph)
{
Boolean[] mstset = new Boolean[graph.V];
node[] edge = new node[graph.V];
int[] parent = new int[graph.V];
for (int o = 0; o < graph.V; o++)
edge[o] = new node();
for (int o = 0; o < graph.V; o++) {
mstset[o] = false;
edge[o].key = Integer.MAX_VALUE;
edge[o].vertex = o;
parent[o] = -1;
}
mstset[0] = true;
edge[0].key = 0;
TreeSet<node> queue = new TreeSet<node>(new comparator());
for (int o = 0; o < graph.V; o++)
queue.add(edge[o]);
while (!queue.isEmpty()) {
node originnode = queue.pollFirst();
mstset[originnode.vertex] = true;
for (newnode iterator : graph.adj[originnode.vertex]) {
if (mstset[iterator.destination] == false) {
if (edge[iterator.destination].key > iterator.weight) {
queue.remove(edge[iterator.destination]);
edge[iterator.destination].key = iterator.weight;
queue.add(edge[iterator.destination]);
parent[iterator.destination] = originnode.vertex;
}
}
}
}
for (int o = 1; o < graph.V; o++)
System.out.println(parent[o] + " "+ "-" + " " + o);
}
public static void main(String[] args)
{
int V = 8;
Graph graph = new Graph(V);
prims g = new prims();
g.addEdge(graph, 0, 1, 10);
g.addEdge(graph, 1, 2, 12);
g.addEdge(graph, 1, 7, 14);
g.addEdge(graph, 1, 5, 6);
g.addEdge(graph, 2, 3, 7);
g.addEdge(graph, 3, 4, 9);
g.addEdge(graph, 4, 5, 11);
g.addEdge(graph, 5, 6, 12);
g.addEdge(graph, 6, 7, 13);
g.prims_mst(graph);
}
}
Output:
0 - 1
3 - 2
4 - 3
5 - 4
1 - 5
5 - 6
1 – 7 gives the Minimum Spanning tree edges in the subgraph
When we use Adjacency List:
Time Complexity: O(ElogV), where E is the number of edges and V is the number of vertices.
When we use Adjacency Matrix:
Time Complexity: O(V2), where V is the number of vertices.
There can be multiple Minimum Spanning Trees having the same minimum sum of weights but considering different edges. Minimum Spanning Tree is one of the most important concepts in graphs that are popular in product based company interview rounds as this has extensive usage in real-world applications.
Frequently Asked Questions
MST stands for Minimum Spanning Tree, which describes the subset of a graph containing all the vertices connected by edges such that the sum of the weights of edges in the subgraph is minimum.
Prim greedily chooses the edges that have the least weight and goes on adding only the least weight edges till we have got the minimum sum of weights.
If the graph consists of lots of edges, i.e. for dense graphs then Prim’s Algorithm is more efficient than Kruskal’s algorithm.
Minimum Spanning Tree is the subgraph of a given graph that spans to all vertices with the minimum possible of the included edges. Prims algorithm tries to greedily choose the least weighted edges to find the Minimum Spanning Tree.
Prim’s Algorithm is quite similar to the Dijkstra algorithm due to its greedily choosing of edges depending on their weights.
Prim’s Algorithm selectively chooses only those edges having minimum weights and includes them in the Minimum Spanning Tree.
Key Takeaways
This blog tried to explain Prim’s Minimum Spanning Tree algorithm starting from the definition of a Spanning tree, real-time applications, Approach and intuition, similarities with Dijkstra’s algorithm, approach and code implementation with the dry run of the algorithm.
To know details about the graph algorithms and practice more such problems you can check out Coding Ninjas CodeStudio.
Hope this article could help you gain detailed concepts on Prim’s Minimum Spanning Tree algorithm.
By Sarthak Dhawan
