Breadth-first search (BFS) Implemetation in Java

Breadth-first seach implementation in java 

import java.util.Iterator;

import java.util.LinkedList;

public class GraphBFS {

     // No. of vertices

     private intvertives;

     //Adjacency Lists - Edges

     private LinkedList<Integer> adj[];

     GraphBFS(int vertices) {

           vertives = vertices;

           adj = newLinkedList[vertices];

           for (inti=0; i<vertices; ++i) {

                adj[i] = new LinkedList<Integer>();

           }

     }

     void addEdge(intv,int w) {

           adj[v].add(w);

     }

     private voidtraverseBFS(int node) {

           /** Mark true if vertices are visited. */

           boolean visited[] = newboolean[vertives];

           /** Create a queue for BFS */

           LinkedList<Integer> queue = newLinkedList<Integer>();

           /** mark start node as visited by default. */

           visited[node] = true;

           queue.add(node);

           while(!queue.isEmpty()) {

                /** poll the first element of queue. */

                node = queue.poll();

                System.out.print(node+" ");

                /** add all the nearest node of processing node. */

                Iterator<Integer> iter = adj[node].listIterator();

                while (iter.hasNext()) {

                     intnext = iter.next();

                     if(!visited[next]) {

                           visited[next] = true;

                           queue.add(next);

                     }

                }

           }

     }

     public static void main(String args[]) {

           /** Create a graph of size . */

           GraphBFS graph = newGraphBFS(4);

           /** Add edges in the graph.*/

           graph.addEdge(0, 1);

           graph.addEdge(0, 2);

           graph.addEdge(1, 2);

           graph.addEdge(2, 0);

           graph.addEdge(2, 3);

           graph.addEdge(3, 2);

           graph.addEdge(3, 1);

           System.out.println("BFS Traversal : ");

           /** start BS from any given node.*/

           graph.traverseBFS(1);

     }

}

Output

BFS Traversal:

1 2 0 3