Prim's Algorithm > Java Program

Analysis of Algorithm

Prim's Algorithm > Java Program

import java.io.*;
class prim
{
public static void main(String args[])throws IOException
{

int size=20;

int nodes,v1,v2,length,i,j,n;
int g[][]=new int[size][size];
DataInputStream in=new DataInputStream(System.in);
System.out.println("Enter number of nodes in graph");
nodes=Integer.parseInt(in.readLine());
System.out.println("Enter number of edges in graph");
n=Integer.parseInt(in.readLine());
for(i=0;i<nodes;i++)
{
for(j=0;j<nodes;j++)
{
g[i][j]=0;
}
}
System.out.println("Enter edge and weight");
for(i=0;i<n;i++)
{
System.out.println("Enter edge by v1 and v2:");
v1=Integer.parseInt(in.readLine());
v2=Integer.parseInt(in.readLine());
System.out.println("enter corresponding weight");
length=Integer.parseInt(in.readLine());
g[v1][v2]=g[v2][v1]=length;
}
operation ob=new operation();
ob.primfun(g,nodes);
}
}

class operation
{
void primfun(int g[][],int nodes)
{
int infinity=9999;
int size=20;
int tree[]=new int[size];
int i,j,k,min_dist,v1=0,v2=0,total=0;
for(i=0;i<nodes;i++)
{
tree[i]=0;
}
System.out.println("minimum spaning tree");
tree[0]=1;
for(k=1;k<=nodes-1;k++)
{
min_dist=infinity;
for(i=0;i<=nodes-1;i++)
{
for(j=0;j<=nodes-1;j++)
{
if(g[i][j]!=0&&((tree[i]==0&&tree[j]!=0)||(tree[i]!=0&&tree[j]==0)))
{
if(g[i][j]<min_dist)
{
min_dist=g[i][j];
v1=i;
v2=j;
}
}
}
}
System.out.println("edge from  "+v1+"to  "+v2+"weight   "+min_dist);
tree[v1]=tree[v2]=1;
total=total+min_dist;
}
System.out.println("Total path length is "+total);
}
}


/*OUTPUT:
Enter number of nodes in graph
5
Enter number of edges in graph
7
Enter edge and weight
Enter edge by v1 and v2:
0
1
enter corresponding weight
10
Enter edge by v1 and v2:
1
2
enter corresponding weight
1
Enter edge by v1 and v2:
2
3
enter corresponding weight
2
Enter edge by v1 and v2:
3
4
enter corresponding weight
3
Enter edge by v1 and v2:
4
0
enter corresponding weight
5
Enter edge by v1 and v2:
1
3
enter corresponding weight
6
Enter edge by v1 and v2:
4
2
enter corresponding weight
7
minimum spaning tree
edge from  0 to  4 weight   5
edge from  3 to  4 weight   3
edge from  2 to  3 weight   2
edge from  1 to  2 weight   1
Total path length is  11          */