When a dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a breadthward motion and uses a queue to remember to retrieve the next vertex to start a search.
Initialize the queue.
We start from visiting S (starting node), and mark it as visited.
We then see an unvisited adjacent node from S. In this example, we have three nodes but alphabetically we choose A, mark it as visited and enqueue it.
Next, the unvisited adjacent node from S is B. We mark it as visited and enqueue it.
Next, the unvisited adjacent node from S is C. We mark it as visited and enqueue it.
Now, S is left with no unvisited adjacent nodes. So, we dequeue and find A.
From A we have D as unvisited adjacent node. We mark it as visited and enqueue it.
At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the program is over.
