Prim's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. It starts with an arbitrary vertex and iteratively adds the shortest edge connecting the current tree to a new vertex until all vertices are included.

In this blog, we will discuss about Prim’s Algorithm in Java. We will discuss what it is and how it works.

Let's understand what Prim's algorithm is!!

Prim's 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

How does Prim’s Algorithm works?

Here are the steps for the working of Prim's algorithm:

Start with an Arbitrary Vertex: Choose an arbitrary vertex to start the minimum spanning tree (MST) construction.

Select the Nearest Vertex: Repeat the following steps until all vertices are included:

Select the vertex not yet in the MST that is closest to any vertex already in the MST.

Add Edge to MST: Add the selected vertex and the corresponding edge to the MST.

Update Distances: Update the distances from the newly added vertex to all other vertices based on the weights of the edges.

Repeat Until Completion: Repeat steps 2-4 until all vertices are included in the MST.

Result: The resulting MST includes all vertices of the graph with the minimum total weight of edges.

Illustration of Prim’s Algorithm

Now, let's see the illustration of Prim's algorithm using an example. Suppose, we have a weighted graph like this:

Step 1: Let us choose an arbitrary vertex, let's choose R.

Step 2: Now, we have to choose and add the shortest edge from vertex R. There are two edges from vertex R that are R to Q with weight 10 and edge R to S with weight 4. Among these edges, the edge R and S has the minimum weight. So, add it to the MST.

Step 3: Again we need to choose the edge with the minimum weight among all the other edges. In this case, the edges S and T and Q and S are such edges. Add them to MST and explore the adjacent of Q, i.e., T and P. So, select the edge S and T and add it to the MST.

Step 4: Now, we can select the edge Q and S, and add it to the MST.

Step 5: Now, we can choose the edges Q and P. Here, we cannot select the edges Q and T as they would create a cycle to the graph. So, choose the edge Q and P and add it to the MST.

So, the graph produced in step 5 is the minimum spanning tree of the given graph. The cost of MST = 4 + 2 + 1 + 3 = 10 units.

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++

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; }

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.

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.

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.

Frequently Asked Questions

What is MST in Prims?

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.

How do you find MST using Prims algorithm?

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.

Which one is better: Prims or Kruskal?

If the graph consists of lots of edges, i.e. for dense graphs then Prim’s Algorithm is more efficient than Kruskal’s algorithm.

What is the minimum spanning tree and explain Prims 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.

What is the algorithm similar to the Dijkstra algorithm?

Prim’s Algorithm is quite similar to the Dijkstra algorithm due to its greedily choosing of edges depending on their weights.

How do you use Prim’s algorithm?

Prim’s Algorithm selectively chooses only those edges having minimum weights and includes them in the Minimum Spanning Tree.

Conclusion

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.