Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

he only catch here is, that, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we divide the vertices into two categories:

• Visited and
• Not visited.

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.

Example:

In the following graph, we start traversal from vertex 2.

When we come to vertex 0, we look for all adjacent vertices of it.

• 2 is also an adjacent vertex of 0.
• If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process.

There can be multiple BFS traversals for a graph. Different BFS traversals for the above graph :
2, 3, 0, 1
2, 0, 3, 1

Implementation of BFS traversal:

Follow the below method to implement BFS traversal.

• Declare a queue and insert the starting vertex.
• Initialize a visited array and mark the starting vertex as visited.
• Follow the below process till the queue becomes empty:
• Remove the first vertex of the queue.
• Mark that vertex as visited.
• Insert all the unvisited neighbours of the vertex into the queue.

Illustration:

Python3

Following is Breadth First Traversal (starting from vertex 2) 
2 0 3 1

Time Complexity: O(V+E), where V is the number of nodes and E is the number of edges.
Auxiliary Space: O(V)

In next article I shall write about BFS for Disconnected Graph.

STAY TUNE.