Prim’s Algorithm in Java

How does Prim’s Algorithm works?

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

1. Start with an Arbitrary Vertex: Choose an arbitrary vertex to start the minimum spanning tree (MST) construction.
2. 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.
3. Add Edge to MST: Add the selected vertex and the corresponding edge to the MST.
4. Update Distances: Update the distances from the newly added vertex to all other vertices based on the weights of the edges.
5. Repeat Until Completion: Repeat steps 2-4 until all vertices are included in the MST.
6. 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

#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.

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.

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.

To know details about the graph algorithms and practice more such problems you can check out Coding Ninjas Coding Ninjas Studio.  
Check out this problem - No of Spanning Trees in a Graph

Hope this article could help you gain detailed concepts on Prim’s Minimum Spanning Tree algorithm.