BFS is a classic algorithm for traversing (visiting) all nodes of a graph or tree.

The easiest way to understand this algorithm is via pseudo-code and an example. The pseudo-code of BFS is as follows:

1. Create a queue Q
2. Mark v as visited and put v into Q
3. While Q is non-empty
4. Remove the head h of Q
5. Mark and en-queue all (unvisited) neighbors of h

Let's assume the graph from the following diagram, Step 0:

At the first step (Step 1), we visit vertex 0. We put this in the visited list and all its adjacent vertices in the queue (3, 1). Furthermore, at Step 2, we visit the element at the front of the queue, 3. Vertex 3 has an unvisited adjacent vertex in 2, so we add that to the back of the queue. Next, at Step 3, we visit the element at the front of the queue, 1. This vertex has a single adjacent vertex (0), but this was visited. Finally, we visit vertex 2, the last from the queue. This one has a single adjacent vertex (3) that was already visited.

In code lines, the BFS algorithm can be implemented as follows:

public class Graph {

  private final int v;
  private final LinkedList<Integer>[] adjacents;

  public Graph(int v) {

    this.v = v;
    adjacents = new LinkedList[v];

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

  public void addEdge(int v, int e) {
    adjacents[v].add(e);
  }

  public void BFS(int start) {

    boolean visited[] = new boolean[v];
    LinkedList<Integer> queue = new LinkedList<>();
    visited[start] = true;

    queue.add(start);

    while (!queue.isEmpty()) {
      start = queue.poll();
      System.out.print(start + " ");

      Iterator<Integer> i = adjacents[start].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }
}

And, if we introduce the following graph (from the preceding diagram), we have the following:

Graph graph = new Graph(4);
graph.addEdge(0, 3);
graph.addEdge(0, 1);
graph.addEdge(1, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
graph.addEdge(3, 2);
graph.addEdge(3, 3);

The output will be 0 3 1 2.