BFS.java

class MyGraph
{
  private int vertices;
  private LinkedList<Integer> adjacency[];

  MyGraph(int v) {
    vertices = v;
    adjacency = new LinkedList[v];
    for (int i=0; i<v; ++i)
      adjacency[i] = new LinkedList();
  }

  // Add an edge into the graph
  void addEdge(int v,int w) {
    adjacency[v].add(w);
  }

  // prints BFS traversal from a given source s
  void traverseBFS(int s) {
    // Set all the vertices as not visited, set as false by default
    boolean visited[] = new boolean[vertices];

    // Create a queue for BFS
    LinkedList<Integer> queue = new LinkedList<Integer>();

    // Set the current node as visited and enqueue it
    visited[s]=true;
    queue.add(s);

    while (queue.size() != 0) {
      // Dequeue a vertex from queue and print the value
      s = queue.poll();
      System.out.print(s+" ");

      // Get all adjacent vertices of the dequeued vertex s. If an adjacent has not been visited, then set it "visited" and enqueue it
      Iterator<Integer> i = adjacency[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        if (!visited[n])
        {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }