Breadth First Search (BFS) Traversal in Data Structure

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

BFS is a smart way to look through data organized in a graph. A graph is a collection of points (called nodes or vertices) connected by lines (called edges).

How BFS Works?

1. Starting Point: Pick a node to start from. This is like choosing where to enter the garden maze.
2. Exploring Nearby: Look at all the nodes directly connected to your starting point. This is like checking all the paths that branch off from where you’re standing.
3. Moving Outward: Once you’ve checked all the nearby nodes, move on to the next set of nodes that are one step farther away.
4. Repeat: Keep going, exploring nodes farther and farther out, until you’ve visited every node.

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 in front of a queue, Remove the front element.
Step 6 – Repeat steps 4 and 6 until the queue becomes empty.
Step 7 – When all elements removed from the queue, it produces the final BFS traversal.

Example Of BFS Graph Traversal

Initialize the queue

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

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.

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

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

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.

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

Conclusion

Breadth-First Search (BFS) is a way to explore all the nodes in a graph level by level. It starts from a chosen node and visits all its neighbors first before moving to the neighbors’ neighbors. BFS is useful for solving puzzles, finding paths in maps, analyzing social networks, and many real-life problems. It ensures we check all possibilities in an organized way, step by step, without missing any node.