BFS

Breadth-First Search (BFS) is a fundamental graph traversal algorithm used to explore nodes and edges of a graph. It starts from a selected node (called the “source” or “root” node) and explores all its neighboring nodes at the present depth level before moving on to nodes at the next depth level. BFS is particularly useful for finding the shortest path in an unweighted graph. Here is a step-by-step explanation of how BFS works:

BFS Algorithm

1. Initialization:
   • Choose a starting node (source node).
   • Create a queue and enqueue the source node.
   • Mark the source node as visited.
2. Traversal:
   • While the queue is not empty:
     • Dequeue a node from the front of the queue (let’s call it current_node).
     • For each unvisited neighbor of current_node:
       • Mark the neighbor as visited.
       • Enqueue the neighbor.

Pseudocode

Here is a simple pseudocode for BFS:

BFS(Graph, start_node):
    create a queue Q
    mark start_node as visited
    enqueue start_node onto Q

    while Q is not empty:
        current_node = Q.dequeue()
        for each neighbor of current_node:
            if neighbor is not visited:
                mark neighbor as visited
                enqueue neighbor onto Q

Example

Consider the following graph:

   A
  / \
 B   C
 |   |
 D   E
  \ /
   F

If we start BFS from node A, the steps would be:

1. Enqueue A and mark it as visited.
2. Dequeue A, enqueue its neighbors B and C, and mark them as visited.
3. Dequeue B, enqueue its neighbor D, and mark it as visited.
4. Dequeue C, enqueue its neighbor E, and mark it as visited.
5. Dequeue D, enqueue its neighbor F, and mark it as visited.
6. Dequeue E, F is already visited.
7. Dequeue F.

The order of visited nodes: A -> B -> C -> D -> E -> F.

Applications

• Shortest Path in an Unweighted Graph: BFS can be used to find the shortest path from the source node to any other node in an unweighted graph.
• Level Order Traversal in Trees: BFS can be used to traverse a tree level by level.
• Finding Connected Components: BFS can help identify connected components in an undirected graph.
• Cycle Detection: BFS can be used to detect cycles in an undirected graph.