Breadth-First Search (BFS) of Graphs

Breadth-First Search (BFS) of Graphs

1. Problem Description
Breadth-First Search (BFS) is an algorithm for traversing or searching a graph (or tree). Its core idea is to access nodes layer by layer, level by level: starting from the source node, it first visits all directly adjacent nodes (first layer), then visits the adjacent nodes of those neighbors (second layer), and so on. BFS is commonly used to solve problems like shortest path (in unweighted graphs) and connectivity checks.

2. Core Ideas and Key Concepts

Role of Queue: BFS uses a queue to store nodes to be visited, ensuring that nodes entering earlier are visited first (FIFO principle), thereby achieving level-order traversal.
Visited Markers: To avoid repeated visits or cycles, it's necessary to record nodes that have already been visited.
Layer-by-Layer Expansion: Starting from the source node, for each layer visited, unvisited neighbors are added to the queue until the queue becomes empty.

3. Algorithm Steps in Detail
Assuming the graph is stored as an adjacency list, with the starting node as s:

Step 1: Initialization

Create a queue queue and enqueue the starting node s.
Create a set visited (e.g., hash table or array) and mark s as visited.

Step 2: Process Queue in a Loop

While the queue is not empty, repeat the following:
1. Dequeue: Remove the front node u from the queue.
2. Visit Node: Perform the target operation on u (e.g., record path, check if destination is reached).
3. Traverse Neighbors: Check all unvisited neighbor nodes v of u:
  - Mark v as visited (to prevent re-enqueueing).
  - Enqueue v.

Step 3: Termination Condition

The algorithm ends when the queue is empty, indicating all nodes reachable from the start have been visited.

4. Example Demonstration
Consider the following graph (undirected, nodes 0~4):

0 — 1
|   |
2 — 3
 \  |
   4

Starting BFS from node 0:

Initial: Queue [0], visited {0}.
Step 1: Dequeue 0, visit 0; neighbors 1, 2 are unvisited, enqueue and mark them. Queue [1, 2], visited {0,1,2}.
Step 2: Dequeue 1, visit 1; neighbors 0 (visited), 3 (unvisited), enqueue 3. Queue [2, 3], visited {0,1,2,3}.
Step 3: Dequeue 2, visit 2; neighbors 0 (visited), 3 (visited), 4 (unvisited), enqueue 4. Queue [3, 4], visited {0,1,2,3,4}.
Step 4: Dequeue 3, visit 3; neighbors 1, 2, 4 (all visited), no new nodes enqueued. Queue [4].
Step 5: Dequeue 4, visit 4; neighbors 2, 3 (visited), queue becomes empty.

Traversal Order: 0 → 1 → 2 → 3 → 4 (layer-by-layer expansion).

5. Code Implementation (Pseudocode)

def BFS(graph, start):
    queue = collections.deque([start])  # Initialize queue
    visited = set([start])             # Visited markers
    
    while queue:
        u = queue.popleft()           # Dequeue
        print(u)                      # Visit node (example operation)
        for v in graph[u]:            # Traverse neighbors
            if v not in visited:
                visited.add(v)
                queue.append(v)       # Enqueue neighbor

6. Application Scenarios and Variants

Shortest Path: In unweighted graphs, the path first reaching the target node via BFS is guaranteed to be the shortest (minimum number of edges).
Connectivity Check: The number of nodes traversed via BFS can determine connected components of a graph.
Extended Functionality: Recording predecessor nodes allows path reconstruction; recording levels enables distance calculation.

Note: For weighted graphs, Dijkstra's algorithm is required; for efficient connectivity checks, Union-Find can also be used.