When a dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a breadthward motion and utilises a queue to remember to retrieve the next vertex to start a search.
As in the example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs the following rules.
- Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
- Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
- Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.
|1||Initialize the queue.|
|2||We start from visiting S (starting node), and mark it as visited.|
|3||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.|
|4||Next, the unvisited adjacent node from S is B. We mark it as visited and enqueue it.|
|5||Next, the unvisited adjacent node from S is C. We mark it as visited and enqueue it.|
|6||Now, S is left with no unvisited adjacent nodes. So, we dequeue and find A.|
|7||From A we have D as unvisited adjacent node. We mark it as visited and enqueue it.|
At this point, there are no unmarked (unvisited) nodes. However, according to the algorithm, we must continue dequeuing in order to obtain all unvisited nodes. The program ends when the queue is empty.