Subscribe to A Kid's scribblings        RSS Feed
-----

Implementing Kruskal's algorithm

Icon Leave Comment
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
       {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("No of points to be dealt with ::");
        int n=Integer.parseInt(br.readLine());
        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)::");
             String s= br.readLine();
             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);
    }
}

0 Comments On This Entry

 

Recent Comments

December 2014

S M T W T F S
 123456
78910111213
1415161718 19 20
21222324252627
28293031   

0 user(s) viewing

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