11. KRUSHKAL'S ALGORITHM

Code:

import java.util.*;

class krushkal

{

            public static void main(String ag[])

             {

             Scanner s=new Scanner(System.in);

                        System.out.println("enter no of vertices");

                        int v=s.nextInt();

                        System.out.println("enter no of edges");

                        int e=s.nextInt();

                        int w[]=new int[e];

                        int x[]=new int[e];

                        int y[]=new int[e];

         for(int i=0;i<e;i++)

                                {       System.out.println("enter edges with weight");

                                    x[i]=s.nextInt();

                                    y[i]=s.nextInt();

                                    w[i]=s.nextInt();    }      

                            for(int i=0;i<e;i++)

                               for(int j=0;j<e-1;j++)

                                  {

                                    if(w[j]>w[j+1])

                                       {          int t=w[j];

                                                w[j]=w[j+1];

                                                w[j+1]=t;

                                                t=x[j];

                                                x[j]=x[j+1];

                                                x[j+1]=t;

                                                t=y[j];

                                                y[j]=y[j+1];

                                                y[j+1]=t;

                                       }}

                              boolean b[]=new boolean[e]; 

                              for(int i=0;i<e;i++)

                                  b[i]=false;

                                  int cost=0;

                            for(int i=0;i<e;i++)

                             {

                                                if(!(b[x[i]]&&b[y[i]]))

                                                    {b[x[i]]=true;

                                                            b[y[i]]=true;

                                                            cost+=w[i];}

                                    }

                             System.out.println("the cost is "+cost)     

                             }

}

OUTPUT:

Need the code??

Download Link= https://www.dropbox.com/s/lw2q2jr8hmylgjv/4%20Kruskals.docx