Kruskal's Algorithm > Java Program

Analysis of Algorithm

Kruskal's Algorithm > Java Program

import java.io.*; 
class kruskal 
{ 
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 
{ 
/*int minimum(int g[][],int nodes) 
{ 
int i,j,small,posi,posj; 
small=9999; 
for(i=0;i<nodes;i++) 
{ 
for(j=0;j<nodes;j++) 
{ 
if(g[i][j]<small) 
{ 
small=g[i][j]; 
posi=i; 
posj=j; 
} 
} 
} 
System.out.println(posi+" to "+posj+" "+g[posi][posj]); 
return g[posi][posj]; 
}
*/ 

void primfun(int g[][],int nodes) 
{ 
int infinity=9999; 
int small=infinity; 
int size=20; 
int tree[]=new int[size]; 
int posi=0,posj=0; 
int i,j,z,x,k,min_dist,v1=0,v2=0,total=0; 
System.out.println("minimum spanning tree"); 
for(z=1;z<=nodes;z++) 
{ 
for(x=1;x<=nodes;x++) 
{ 
if(g[z][x]!=0&&g[z][x]<small) 
{ 
posi=z; 
posj=x; 
small=infinity; 
} 
} 
System.out.println(posi+" to "+posj+" weight "+g[posi][posj]); 
tree[posi]=tree[posj]=1; 
total=total+g[posi][posj]; 
g[posi][posj]=0; 
} 
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 spanning 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
*/