Subscribe to A Kid's scribblings

## Implementing Kruskal's algorithm

Kruskal's algorithm is designed to find the shortest path covering all the vertices in a graph. Here is a implementation of it using Java.

```package gojabe;
import java.io.*;
public class kruskals_algorithm
{
public static void main(String args[])throws Exception
{
System.out.println("No of points to be dealt with ::");
int v[][]=new int[n][n];
int i=0,j=0,k=0;
while(true)
{
System.out.println("Enter the coordinates along with the distances (Pt. A,Pt. B,Distance)::");
if(s.equals("over"))
break;
String data[]=s.split(",");
i=Integer.parseInt(data[0]);
j=Integer.parseInt(data[1]);
k=Integer.parseInt(data[2]);
if(v[i-1][j-1]==0)
{
v[i-1][j-1]=k;
v[j-1][i-1]=k;
}
}
kruskal(v,n);
}
public static void kruskal(int W[][],int n)
{
int i=0,j=0,k=0,len=(n*(n-1))/2;
int t[]=new int[len];
String path[]=new String[len];
for(i=0;i<len;i++)
path[i]="";
for(i=0;i<n;i++)
W[i][i]=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(W[i][j]!=0 && k<len)
{
t[k]=W[i][j];
path[k]=(i+1)+"-"+(j+1);
k++;
W[i][j]=0;
W[j][i]=0;
}
i=0;j=0;k=0;String p;
for(j=1;j<len-1;j++)
{
k=t[j];
p=path[j];
i=j-1;
while(i!=-1 && k<t[i])
{
t[i+1]=t[i];
path[i+1]=path[i];
i--;
}
t[i+1]=k;
path[i+1]=p;
}
p=path[0]+"";
boolean flag_1=false,flag_2=false;
for(k=1;k<len;k++)
{
if(path[k].length()>0)
{
flag_1=search(p,path[k].charAt(0)+"",path[k].charAt(2)+"");
flag_2=search_loop(path[k].charAt(0)+"",path[k].charAt(2)+"",path,k);
if(flag_1 || flag_2)
{
t[k]=0;
path[k]="";
}
else
{
p=p+"-"+path[k];
}
}
}
display(t,path,len,n);
}
public static boolean search(String db,String a,String b)
{
boolean result=false;
if(db.length()>0)
{
String t[]=db.split("-");
int n=t.length;
int i=0,found_a=0,found_b=0;
for(i=0;i<n;i++)
if(t[i].equals(a))
found_a++;
for(i=0;i<n;i++)
if(t[i].equals(b))
found_b++;
if(found_a==2 || found_b==2)
result=true;
}
return result;
}
public static boolean search_loop(String a,String b,String p[],int n)
{
int flag[]=new int[n];
int i=0,k=0;
boolean res=false;
String temp=a;
while(i<n)
{
if(flag[i]==0 && p[i].length()>0)
{
if((p[i].charAt(0)+"").equals(temp))
{
temp=p[i].charAt(2)+"";
flag[k++]=1;
i=-1;
}
else if((p[i].charAt(2)+"").equals(temp))
{
temp=p[i].charAt(0)+"";
flag[k++]=1;
i=-1;
}
if(temp.equals(b))
{
res=true;
break;
}
}
i++;
}
return res;
}
public static void display(int d[],String p[],int n,int num)
{
String path="",temp="";int j=0;
int dist=d[0];
int i=0,k=1;
for(i=0;i<n;i++)
if(p[i].length()>0)
{
temp=p[i].charAt(2)+"";
dist=d[i];
break;
}
path=p[i];
for(i=i+1;i<n && k<n;i++)
{
if(p[i].length()>0)
{
if(temp.equals(p[i].charAt(0)+""))
{
path=path+"-"+p[i].charAt(2)+"";
temp=p[i].charAt(2)+"";
dist+=d[i];
p[i]="";
d[i]=0;
k++;
i=0;
}
else if(temp.equals(p[i].charAt(2)+""))
{
path=path+"-"+p[i].charAt(0)+"";
temp=p[i].charAt(0)+"";
dist+=d[i];
p[i]="";
d[i]=0;
k++;
i=0;
}
}
}
if(path.length()-1<num)
{
for(i=0;i<n;i++)
if(p[i].length()>0)
{
temp=p[i].charAt(0)+"";
break;
}
path=p[i];k=0;
for(i=i+1;i<n && k<n;i++)
{
if(p[i].length()>0)
{
if(temp.equals(p[i].charAt(0)+""))
{
path=path+"-"+p[i].charAt(2)+"";
temp=p[i].charAt(2)+"";
dist+=d[i];
p[i]="";
d[i]=0;
k++;
i=0;
}
else if(temp.equals(p[i].charAt(2)+""))
{
path=path+"-"+p[i].charAt(0)+"";
temp=p[i].charAt(0)+"";
dist+=d[i];
p[i]="";
d[i]=0;
k++;
i=0;
}
}
}
}
System.out.println("The shortest path covering all the vertices are ::  "+path);
System.out.println("The distance of shortest path ::   "+dist);
}
}

```

S M T W T F S
12
3456789
10111213141516
17181920212223
24 252627282930

### 0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)