Breadth First Search Algorithm

BFS is a powerful graph traversal technique used to systematically explore all nodes of a graph or tree. It plays a crucial role in various applications, including network routing, shortest path finding

Traversal Technique

BFS explores a graph in a breadth-wise manner. It starts at a specified node (often the root) and systematically visits all nodes at the current level before moving to the next level.

Queue Data Structure

The queue maintains the order in which nodes are visited, ensuring that nodes at the current level are explored before moving to deeper levels.

BFS Algorithm (Step-by-Step)

1. Initialize a queue and a visited set (or array).
2. Enqueue the starting node and mark it as visited.
3. While the queue is not empty:
   • Dequeue the front node.
   • Process it (print/store).
   • Enqueue all unvisited neighbors, marking them as visited.
4. Repeat until no nodes remain in the queue.

Example (Graph Traversal)

Graph:

          1 -- 2 -- 5
          |    |
          3 -- 4
          

Start Node: 1

Traversal Order (BFS):

1 → 2 → 3 → 5 → 4

Explanation:

• Start at 1 → enqueue [1]
• Visit 1, enqueue neighbors [2, 3]
• Visit 2, enqueue [5, 4]
• Visit 3 (already added neighbors)
• Visit 5 → done
• Visit 4 → done

Time and Space Complexity

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph. The space complexity is also O(V) due to the storage requirements of the queue and visited set.

Properties of BFS:

Shortest Path Finding

Cycle Detection

Level Order Traversal

Bi-directional Search