Breadth First Search (BFS) Traversal in Data Structure

Breadth-first search graph traversal techniques use a queue data structure as an auxiliary data structure to store nodes for further processing. The size of the queue will be the maximum total number of vertices in the graph.

Steps to implement BFS traversal

Step 1 – First define a Queue of size n. Where n is the total number of vertices in the graph.
Step 2 – Select any vertex which is a starting point from where traversal will start.
Step 3 – Visit starting vertex and insert it into the Queue.
Step 4 – Visit all the non-visited adjacent vertices which is connected to it and insert all non-visited vertices into the Queue.
Step 5 – When there is no new vertex to be visited from the element which is top in a queue, Remove the top element which is the vertex from the queue.
Step 6 – Repeat steps 4 and 6 until the queue becomes empty.
Step 7 – When all elements removed from the queue, then produce the final spanning tree by removing unused edges from the graph.

Example Of BFS Graph Traversal

Initialize the queue

Breadth First Search traversal

We start visiting from vertex 12 that can be considered as starting node, and mark it as visited.

Breadth First Search traversal in data structure

Now we will see an unvisited adjacent node from 12. In this example, we have three nodes and we can visit anyone. here we are traversing from left to right. We choose 5 and mark it as visited and enqueue it.

bfs graph traversal

Next, visit the unvisited adjacent node from 12 to 23 . We mark it as visited and enqueue it.

Breadth First Search traversal

Next, the unvisited adjacent node from 12 is 3. We mark it as visited and enqueue it.

BFS Graph traversal

Now, all the connected adjacent node from 12 is traversed and no unvisited adjacent nodes left. So, we dequeue and find all connect vertex from 5.

Breadth First Search traversal technique

From 5 we have 25 as unvisited adjacent node. We mark it as visited and enqueue it.

Now if all nodes visited, we will dequeue all nodes from queue.

So BFS Traversal output is : 12, 5, 23, 3, 25

Complexity Analysis of BFS

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity: O(V).
Since, an extra visited array is needed of size V.

Applications of BFS

  • Finding the Shortest path in an unweighted graph
  • Find a solution to a game with the least number of moves. In such a scenario each state of the game can be represented by a node and state transitions as edges
  • Finding Connected Components in an unweighted graph
  • Level Order Traversal in Tree
  • Find the shortest paths in graphs with weights 0/1