Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.LinkedList;
- import java.util.Queue;
- import java.util.Stack;
- /*
- +offer(element: E): boolean // Inserting an element
- +poll(): E // Retrieves the element and returns NULL if queue is empty
- +remove(): E // Retrieves and removes the element and throws an Exception if queue is empty
- +peek(): E // Retrieves,but does not remove, the head of this queue, returning null if this queue is empty.
- +element(): E // Retrieves, but does not remove, the head of this queue, throws an exception if the queue is empty.
- */
- public class BFS { // O(|V|+ E)
- public static void BFS(ArrayList<Integer>[] graph) {
- Queue<Integer> queue = new LinkedList<Integer>();
- int INF = Integer.MAX_VALUE;
- int stepCount = 0;
- int[] dist = new int[graph.length];
- /*
- w (white) - untouched vertex
- g (grey) - visited vertex
- b (black) - finished vertex
- */
- char[] color = new char[graph.length];
- for (int i = 0; i < dist.length; i++) {
- dist[i] = INF;
- }
- for (int i = 0; i < color.length; i++) {
- color[i] = 'w';
- }
- int currVer = 0; // start from 0 vertex
- dist[0] = stepCount; // distance it itself
- queue.offer(0); // insert the fist working element
- color[0] = 'g'; // start point to work with
- while(!queue.isEmpty() /*|| currVer == graph.length-1*/){
- System.out.print("(" + currVer + ")" + "->");
- /*
- * Iterate on the current working vertex neighbors
- * look up for that neighbors which havent been visited before,
- * then mark (paint) them as such, and push to queue
- */
- for (Integer k : graph[currVer]){
- // "preform steps" only on white neighbors inserted - which not yet visited
- if(color[k] != 'b' && color[k] != 'g'){
- color[k] = 'g'; // paint the neighbors
- queue.offer(k); // insert the neighbors to the queue
- }
- } // for each
- color[currVer] = 'b'; // paint finished to the current working vertex
- if(!queue.isEmpty()){
- currVer = queue.poll(); // pull up the next in line vertex and make it current working vertex
- }
- //dist[currVer] = stepCount;// lo nahon
- //++stepCount;
- }
- color[currVer] = 'b'; // paint the last visited vertex manually, cause it remains grey
- System.out.println(Arrays.toString(color));
- System.out.println(Arrays.toString(dist));
- } // BFS
- public static void main(String[] args) {
- ArrayList<Integer>[] tree = new ArrayList[8];
- for (int i = 0; i < tree.length; i++) {
- tree[i] = new ArrayList<>();
- }
- tree[0].add(1);
- tree[0].add(4);
- tree[1].add(0);
- tree[1].add(4);
- tree[1].add(2);
- //tree[1].add(3);//<<
- tree[2].add(1);
- tree[2].add(7);
- //tree[3].add(1);//<<
- tree[4].add(0);
- tree[4].add(1);
- tree[4].add(5);
- tree[4].add(6);
- tree[5].add(4);
- tree[5].add(7);
- tree[6].add(4);
- tree[7].add(2);
- tree[7].add(5);
- BFS(tree);
- /////////////////////////////////////////////////////////////////////
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement