Java Coding Problems

123. Breadth-first search

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