Kruskal

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package algorithm;

import java.io.File;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;


/**
 *
 * @author acer
 */
public class kruskal {

    public static int edge;

    public static int node;

    public static int[] color;
    public static int[] d;

    public static int[] parent;

      //

      public static ArrayList<HashSet> A = new ArrayList<HashSet>();
    public static HashSet<Integer> src = new HashSet<Integer>();
    public static HashSet<Integer> dst = new HashSet<Integer>();
    public static int sum;

    public static int[] vertices=new int[] {0,1,2,3,4,5,6,7,8};
     public static int[] weight;

     public static int[] u ;
     public static int[] v ;

    public static int[][] matrix;
    //public static int node;

    //static int[][] adjMatrix=new int[][]{{0,1,1,0,0,0},{0,0,0,0,0,1},{0,0,0,1,0,0},{1,1,0,0,0,0},{0,0,0,0,0,1}};;


     public static void main(String [] args) {
         try{
                Scanner scn=new Scanner(new File("E:\\kruskal.txt"));
                String[] splitA;
                String temp=scn.nextLine();
                node=Integer.parseInt(temp);

                 edge=Integer.parseInt(scn.nextLine());

             //   out.println(v);

                weight=new int [edge+1];
                matrix=new int[node+1][node+1];

               u=new int[edge+1 ];
                v=new int[edge+1 ];

                int count=1;
                while(scn.hasNext())
                {
                String line=scn.nextLine();
                splitA=line.split(",");
                int x=Integer.parseInt(splitA[0]);
                int y=Integer.parseInt(splitA[1]);
                int w=Integer.parseInt(splitA[2]);
                u[count]=x;
                v[count]=y;
                matrix[x][y]=w;
                matrix[y][x]=w;
                weight[count]=w;
                count++;
                }

                for(int k:u){
                    System.out.print(k+" ");
                }
                System.out.println();
                for(int k:v){
                    System.out.print(k+" ");
                }

                 System.out.println();
                for(int i=1;i<matrix.length;i++){
                    for(int j=0;j<matrix.length;j++){
                        System.out.print(matrix[i][j]+",");
                    }
                    System.out.println();
                }

                System.out.println(findIndex(1,vertices));

         }

                catch(Exception e) {
                   e.printStackTrace();
                }

         Queue<Integer> q=new LinkedList<Integer>();
         PriorityQueue<Integer> pQueue =new PriorityQueue<Integer>();

         for(int j=1;j<=edge;j++){
         System.out.print(weight[j]+" ");
         pQueue.add(weight[j]);
         }
         System.out.println("Peek"+pQueue.peek());

         for(int i=0;i<=node;i++){
             HashSet<Integer>set=new HashSet<Integer>();

              set.add(i);
              A.add(set);
         }
         int sum=0;
         for(int i=1;i<=edge;i++){

             int tempW=pQueue.poll();
             System.out.println("echo "+tempW);
             int index=findIndex(tempW,weight);
             System.out.println("index"+index);
             src=A.get(u[index]);
             dst=A.get(v[index]);

             HashSet tempSet=new HashSet();

             Iterator iter_src = src.iterator();

            Object srcfirst = iter_src.next();

            Iterator iter_dst = dst.iterator();

            Object dstfirst = iter_dst.next();
             if(srcfirst!=dstfirst){
                 System.out.println(u[index]+" "+v[index]);
                 union(src,dst);
                 System.out.println("src "+src);
                 union(tempSet, src);
                 sum = sum +tempW;
        } else {
            sum += 0;
        }
             }

             System.out.println("Sum "+sum);
         }





     public static int findIndex(int value,int [] arr) {
         int index=-1;
         for(int i=0;i<arr.length;i++){
             if(value==arr[i]){
                 index=i;
             }
         }
        return index;
    }

     public static void union(HashSet a,HashSet b) {
        a.addAll(b);
        Iterator <Integer>i=a.iterator();
            while(i.hasNext()){
                A.get(i.next()).addAll(a);
            }
    }
}