Breadth First Search or BFS for a Graph

Breadth-First Search (BFS) is a graph traversal algorithm used to explore nodes and edges in a graph systematically. It starts from a given source node and explores all its neighbors before moving on to their neighbors, ensuring the search progresses level by level.

Key Characteristics of BFS

1. Level-order traversal: Visits nodes layer by layer (or distance by distance) from the source.
2. Uses a queue: It relies on the FIFO (First In, First Out) principle for node exploration.
3. Time complexity: $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges.
4. Space complexity: $O(V)$, for the visited list and queue.
5. Applicable for:
   • Finding the shortest path in an unweighted graph.
   • Checking graph connectivity.
   • Solving puzzles and problems like maze traversal.

BFS Algorithm

1. Start with the source node.
2. Mark the source node as visited.
3. Add the source node to a queue.
4. While the queue is not empty:
   • Remove the front node from the queue.
   • Visit all its unvisited neighbors, mark them as visited, and add them to the queue.

Python Implementation

Output for the Example

Given the graph above, the BFS traversal starting from 'A' is:

Explanation

1. Start at 'A', visit its neighbors 'B' and 'C'.
2. Move to 'B', visit its neighbors 'D' and 'E'.
3. Move to 'C', visit its neighbor 'F'.
4. Continue until all nodes are visited.

Advantages

• Guarantees the shortest path in an unweighted graph.
• Simple and easy to implement.

Disadvantages

• Requires extra memory for the queue.
• May become slow for dense or large graphs.

BFS is foundational for solving many graph-based problems, such as finding connected components, detecting cycles, and pathfinding in games.