Prims Algorithms Implementation In Java

Prims Algorithms Implementation In Java
MINIMUM COST SPANNING TREE
Write a program in java using prims algorithms for Minimum Cost Spanning Tree 

import java.io.*; 
import java.util.*; 
 
class Graph 
{ int weight[][]=new int[20][20]; 
 int visited[]=new int [20]; 
 int d[]=new int[20]; 
 int p[]=new int[20]; 
 int v,e; 
 void creategraph()throws IOException 
 { 
 int i,j,a,b,w; 
 BufferedReader in=new BufferedReader( new InputStreamReader(System.in)); 
 System.out.print(“nEnter number of vertices :”); 
 v=Integer.parseInt(in.readLine()); 
 System.out.print(“nEnter number of Edges :”); 
 e=Integer.parseInt(in.readLine()); 
 for ( i=1;i<=v;i++) 
 for( j=1;j<=v;j++) 
 weight[i][j]=0; 
 
 for (i=1;i<=v;i++) 
 { 
 p[i]=visited[i]=0; 
 d[i]=32767; 
 } 
 for ( i=1;i<=e;i++) 
 { 
 System.out.print(“nEnter edge a,b and weight w :”); 
 a=Integer.parseInt(in.readLine()); 
 b=Integer.parseInt(in.readLine()); 
 w=Integer.parseInt(in.readLine()); 
 weight[a][b]=weight[b][a]=w; 
 } 
 
 } 
 
 void algo ()throws IOException 
 { 
 creategraph(); 
 int current,total,mincost,i; 
 current=1;d[current]=0; 
 total=1; 
 visited[current]=1; 
 while(total!=v) 
 { 
 for (i=1;i<=v;i++) 
 { 
 if(weight[current][i]!=0) 
 if(visited[i]==0) 
 if(d[i]>weight[current][i]) 
 { 
 d[i]=weight[current][i]; 
 p[i]=current; 
 } 
 } 
 mincost=32767; 
 for (i=1;i<=v;i++) 
 { 
 if(visited[i]==0) 
 if(d[i]<mincost) 
 { 
 mincost=d[i]; 
 current=i; 
 } 
 } 
 visited[current]=1; 
 total++; 
 } 
 mincost=0; 
 for(i=1;i<=v;i++) 
 mincost=mincost+d[i]; 
 System.out.print(“n Minimum cost=”+mincost); 
 System.out.print(“n Minimum Spanning tree is”); 
 
 for(i=1;i<=v;i++) 
 System.out.print(“n vertex” +i+”is connected to”+p[i]); 
} 
} 
class prims 
{ 
public static void main(String args[])throws IOException 
{ 
 Graph g=new Graph(); 
 g.algo(); 
} 
} 
 
/* 
 
Enter number of vertices :5 
 
Enter number of Edges :7 
 
Enter edge a,b and weight w :1 
2 
2 
 
Enter edge a,b and weight w :1 
5 
8 
 
Enter edge a,b and weight w :2 
3 
6 
 
Enter edge a,b and weight w :2 
4 
12 
 
Enter edge a,b and weight w :2 
5 
7 
 
Enter edge a,b and weight w :4 
5 
4 
 
Enter edge a,b and weight w :3 
4 
10 
 
 Minimum cost=19 
 Minimum Spanning tree is 
 vertex1is connected to0 
 vertex2is connected to1 
 vertex3is connected to2 
 vertex4is connected to5 
 vertex5is connected to2 
*/