Advertisement
Guest User

Untitled

a guest
Jun 28th, 2017
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.12 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. import java.util.Stack;
  6. /*
  7. +offer(element: E): boolean // Inserting an element
  8.  
  9. +poll(): E // Retrieves the element and returns NULL if queue is empty
  10.  
  11. +remove(): E // Retrieves and removes the element and throws an Exception if queue is empty
  12.  
  13. +peek(): E // Retrieves,but does not remove, the head of this queue, returning null if this queue is empty.
  14.  
  15. +element(): E // Retrieves, but does not remove, the head of this queue, throws an exception if the queue is empty.
  16.  */
  17.  
  18. public class BFS { // O(|V|+ E)
  19.  
  20.    
  21.     public static void BFS(ArrayList<Integer>[] graph) {
  22.        
  23.         Queue<Integer> queue = new LinkedList<Integer>();
  24.        
  25.         int INF = Integer.MAX_VALUE;
  26.         int stepCount = 0;
  27.        
  28.         int[]  dist  = new  int[graph.length];
  29.         /*
  30.             w (white) - untouched vertex
  31.             g (grey)  - visited vertex
  32.             b (black) - finished vertex
  33.          */
  34.         char[] color = new char[graph.length];
  35.        
  36.        
  37.        
  38.         for (int i = 0; i < dist.length; i++) {
  39.             dist[i] = INF;
  40.         }
  41.         for (int i = 0; i < color.length; i++) {
  42.             color[i] = 'w';
  43.         }
  44.        
  45.         int currVer = 0; // start from 0 vertex
  46.         dist[0] = stepCount; // distance it itself
  47.         queue.offer(0); // insert the fist working element
  48.         color[0] = 'g'; // start point to work with
  49.        
  50.        
  51.         while(!queue.isEmpty() /*|| currVer == graph.length-1*/){
  52.             System.out.print("(" + currVer + ")" + "->");
  53.             /*
  54.              * Iterate on the current working vertex neighbors
  55.              * look up for that neighbors which havent been visited before,
  56.              * then mark (paint) them as such, and push to queue
  57.              */
  58.             for (Integer k : graph[currVer]){
  59.                
  60.                 // "preform steps" only on white neighbors inserted - which not yet visited
  61.                 if(color[k] != 'b' && color[k] != 'g'){
  62.                     color[k] = 'g';     // paint the neighbors
  63.                     queue.offer(k);     // insert the neighbors to the queue
  64.                 }
  65.             } // for each
  66.            
  67.             color[currVer] = 'b'; // paint finished to the current working vertex
  68.            
  69.             if(!queue.isEmpty()){
  70.                 currVer = queue.poll(); // pull up the next in line vertex and make it current working vertex
  71.             }
  72.  
  73.             //dist[currVer] = stepCount;// lo nahon
  74.             //++stepCount;
  75.            
  76.         }  
  77.         color[currVer] = 'b'; // paint the last visited vertex manually, cause it remains grey
  78.        
  79.        
  80.        
  81.         System.out.println(Arrays.toString(color));
  82.         System.out.println(Arrays.toString(dist));
  83.        
  84.        
  85.     } // BFS
  86.    
  87.    
  88.    
  89.    
  90.    
  91.    
  92.    
  93.    
  94.    
  95.    
  96.    
  97.    
  98.    
  99.    
  100.    
  101.     public static void main(String[] args) {
  102.  
  103.         ArrayList<Integer>[] tree = new ArrayList[8];
  104.  
  105.         for (int i = 0; i < tree.length; i++) {
  106.             tree[i] = new ArrayList<>();
  107.         }
  108.  
  109.         tree[0].add(1);
  110.         tree[0].add(4);
  111.        
  112.         tree[1].add(0);
  113.         tree[1].add(4);
  114.         tree[1].add(2);
  115.         //tree[1].add(3);//<<
  116.        
  117.         tree[2].add(1);
  118.         tree[2].add(7);
  119.        
  120.         //tree[3].add(1);//<<
  121.  
  122.         tree[4].add(0);
  123.         tree[4].add(1);
  124.         tree[4].add(5);
  125.         tree[4].add(6);
  126.  
  127.         tree[5].add(4);
  128.         tree[5].add(7);
  129.  
  130.         tree[6].add(4);
  131.        
  132.         tree[7].add(2);
  133.         tree[7].add(5);
  134.        
  135.        
  136.         BFS(tree);
  137.         /////////////////////////////////////////////////////////////////////
  138.  
  139.  
  140.  
  141.  
  142.  
  143.     }
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement