Prims Algorithms Implementation In Java
MINIMUM COST SPANNING TREE
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
*/
You Might Also Like :
