Java Program to Implement Prim's Minimum Spanning Tree

A Spanning tree of a connected graph G is a acyclic subgraph of graph G that includes all vertices of G. A minimum spanning tree of connected graph G is a graph that consists of minimum weights or edge costs to reach each of the vertices . Start with any one vertex and grow the tree one vertex at a time to produce minimum spanning tree with least total weight or edge cost.We are using Prim's algorithm to find the minimum spanning tree .

Also Read : Java Program to Implement Dijkstra's Shortest Path Algorithm

Take an Example for the Image below , We have four vertices a , b , c , d with their Cost weights are given in their edges.Source vertex is - Vertex 'a' which is marked.

First we write the Cost matrix as :

1 2 3 4
1 i 3 i 7
2 3 i 4 2
3 i 4 i 5
4 7 2 5 i

The Minimum Spanning Tree for the above example is :
a-->b : cost : 3
b-->d : cost : 2
b-->c : cost : 4

Among all edges of vertex a ,we need to find the least or minimum cost edge & mark that vertex then we go to the next vertex .Similarly find the minimum edge for the next vertex so on until we cover (travel) all vertices with minimum cost to form Minimum Spanning Tree. Greedy part of this Algorithm is to find the minimum cost edge and growing the tree dynamically.

Java Code to Implement Prim's Minimum Spanning Tree :


import java.util.*;
public class Prims
{
    public  int isVisited[] = new int[15];
    public  int cost[][] = new int[10][10];
    public int minimum_cost;
     
    public void calc(int n)
    {   
        int flag[] = new int[n+1];
        int i,j,min=999,num_edges=1,a=1,b=1,minpos_i=1,minpos_j=1;
         
        while(num_edges < n)
        {    
            
            for(i=1,min=999;i<=n;i++)
             for(j=1;j<=n;j++)
              if(this.cost[i][j]<min)
                if(this.isVisited[i]!=0)
                 {
                      min=this.cost[i][j];
                      a=minpos_i=i;
                      b=minpos_j=j;
                 }
 				if(this.isVisited[minpos_i]==0 || this.isVisited[minpos_j]==0)
             	{
  					  System.out.println("Edge Number \t"+num_edges+"\t from Vertex \t"+a+"\t  to Vertex \t"+b+"-mincost:"+min+" \n");
                      this.minimum_cost=this.minimum_cost+min;
        			  num_edges=num_edges+1; 
                      this.isVisited[b]=1;
                }
                   this.cost[a][b]=this.cost[b][a]=999;   
        
        
        }   
         
    }
    
    public static void main(String args[])
    {
        int nodes,i,j;
        Scanner in = new Scanner(System.in);
        System.out.println("Enter the Number of Nodes \n");
        nodes = in.nextInt();
        Prims p = new Prims();
        System.out.println("Enter the Cost Matrix Weights : \n");
        for(i=1;i<=nodes;i++)
          for(j=1;j<=nodes;j++)
          {
            p.cost[i][j]=in.nextInt();
            if(p.cost[i][j]==0)
              p.cost[i][j]=999;
          }
       
        p.isVisited[1]=1; // Initialization 
        p.calc(nodes);
  
         
    }   
}

Please Click and Drag from the beginning to End of the above Source code for Selection and Copying.

To Compile and Run :

javac Prims.java
java Prims

Enter the Number of Nodes : 4
Enter the Cost Matrix Weights :
0 3 999 7
3   0   4 2
999 4   0   5
7   2   5   0

Edge Number 1 from Vertex 1 to Vertex 2 -mincost:3

Edge Number 2 from Vertex 2 to Vertex 4 -mincost:2

Edge Number 3 from Vertex 2 to Vertex 3 -mincost:4

Prim's Minimum Spanning Tree containing Edges are numbered with its two vertices and minimum costs are shown in the Output above.

Please Note : Once we Visit a node or an edge ,we make the cost 999 so that it should not visit that same node or an edge again . And also this.isVisited[] ,this.minimum_cost and this.cost[][] basically refers to current object p's isVisited Array ,Minimum_Cost and Cost matrix .Thanks and Enjoy Coding.

If you have any Comments please let me know by Commenting below .