SHARE
TWEET

Kruskal

FahimFaisal Nov 12th, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package algorithm;
  7.  
  8. import java.io.File;
  9. import java.util.ArrayList;
  10. import java.util.HashSet;
  11. import java.util.Iterator;
  12. import java.util.LinkedList;
  13. import java.util.PriorityQueue;
  14. import java.util.Queue;
  15. import java.util.Scanner;
  16. import java.util.TreeSet;
  17.  
  18.  
  19. /**
  20.  *
  21.  * @author acer
  22.  */
  23. public class kruskal {
  24.    
  25.     public static int edge;
  26.  
  27.     public static int node;
  28.  
  29.     public static int[] color;
  30.     public static int[] d;
  31.  
  32.     public static int[] parent;
  33.    
  34.       //
  35.      
  36.       public static ArrayList<HashSet> A = new ArrayList<HashSet>();
  37.     public static HashSet<Integer> src = new HashSet<Integer>();
  38.     public static HashSet<Integer> dst = new HashSet<Integer>();
  39.     public static int sum;
  40.    
  41.     public static int[] vertices=new int[] {0,1,2,3,4,5,6,7,8};
  42.      public static int[] weight;
  43.      
  44.      public static int[] u ;
  45.      public static int[] v ;
  46.    
  47.     public static int[][] matrix;
  48.     //public static int node;
  49.    
  50.     //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}};;
  51.  
  52.  
  53.      public static void main(String [] args) {
  54.          try{
  55.                 Scanner scn=new Scanner(new File("E:\\kruskal.txt"));
  56.                 String[] splitA;
  57.                 String temp=scn.nextLine();
  58.                 node=Integer.parseInt(temp);
  59.                
  60.                  edge=Integer.parseInt(scn.nextLine());
  61.                  
  62.              //   out.println(v);
  63.              
  64.                 weight=new int [edge+1];
  65.                 matrix=new int[node+1][node+1];
  66.                
  67.                u=new int[edge+1 ];
  68.                 v=new int[edge+1 ];
  69.                
  70.                 int count=1;
  71.                 while(scn.hasNext())
  72.                 {
  73.                 String line=scn.nextLine();
  74.                 splitA=line.split(",");
  75.                 int x=Integer.parseInt(splitA[0]);
  76.                 int y=Integer.parseInt(splitA[1]);
  77.                 int w=Integer.parseInt(splitA[2]);
  78.                 u[count]=x;
  79.                 v[count]=y;
  80.                 matrix[x][y]=w;
  81.                 matrix[y][x]=w;
  82.                 weight[count]=w;
  83.                 count++;
  84.                 }
  85.                
  86.                 for(int k:u){
  87.                     System.out.print(k+" ");
  88.                 }
  89.                 System.out.println();
  90.                 for(int k:v){
  91.                     System.out.print(k+" ");
  92.                 }
  93.                
  94.                  System.out.println();
  95.                 for(int i=1;i<matrix.length;i++){
  96.                     for(int j=0;j<matrix.length;j++){
  97.                         System.out.print(matrix[i][j]+",");
  98.                     }
  99.                     System.out.println();
  100.                 }
  101.                
  102.                 System.out.println(findIndex(1,vertices));
  103.                
  104.          }
  105.          
  106.                 catch(Exception e) {
  107.                    e.printStackTrace();
  108.                 }
  109.          
  110.          Queue<Integer> q=new LinkedList<Integer>();
  111.          PriorityQueue<Integer> pQueue =new PriorityQueue<Integer>();
  112.        
  113.          for(int j=1;j<=edge;j++){
  114.          System.out.print(weight[j]+" ");
  115.          pQueue.add(weight[j]);
  116.          }
  117.          System.out.println("Peek"+pQueue.peek());
  118.          
  119.          for(int i=0;i<=node;i++){
  120.              HashSet<Integer>set=new HashSet<Integer>();
  121.              
  122.               set.add(i);
  123.               A.add(set);
  124.          }
  125.          int sum=0;
  126.          for(int i=1;i<=edge;i++){
  127.              
  128.              int tempW=pQueue.poll();
  129.              System.out.println("echo "+tempW);
  130.              int index=findIndex(tempW,weight);
  131.              System.out.println("index"+index);
  132.              src=A.get(u[index]);
  133.              dst=A.get(v[index]);
  134.              
  135.              HashSet tempSet=new HashSet();
  136.              
  137.              Iterator iter_src = src.iterator();
  138.  
  139.             Object srcfirst = iter_src.next();
  140.            
  141.             Iterator iter_dst = dst.iterator();
  142.  
  143.             Object dstfirst = iter_dst.next();
  144.              if(srcfirst!=dstfirst){
  145.                  System.out.println(u[index]+" "+v[index]);
  146.                  union(src,dst);
  147.                  System.out.println("src "+src);
  148.                  union(tempSet, src);
  149.                  sum = sum +tempW;
  150.         } else {
  151.             sum += 0;
  152.         }
  153.              }
  154.              
  155.              System.out.println("Sum "+sum);
  156.          }
  157.      
  158.          
  159.      
  160.          
  161.      
  162.      public static int findIndex(int value,int [] arr) {
  163.          int index=-1;
  164.          for(int i=0;i<arr.length;i++){
  165.              if(value==arr[i]){
  166.                  index=i;
  167.              }
  168.          }
  169.         return index;
  170.     }
  171.      
  172.      public static void union(HashSet a,HashSet b) {
  173.         a.addAll(b);
  174.         Iterator <Integer>i=a.iterator();
  175.             while(i.hasNext()){
  176.                 A.get(i.next()).addAll(a);
  177.             }
  178.     }
  179. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top