4.3.3 Combining Queue and Graph to Perform BFS
Computational Structures
Breadth-First Search (BFS) is another fundamental algorithm used to explore or traverse through a graph or tree structure. Unlike Depth-First Search, BFS uses a queue data structure to keep track of the vertices or nodes that need to be visited. This method is particularly useful when we need to explore all nodes at the present depth level before moving on to nodes at the next depth level, making it ideal for situations where we need to find the shortest path or explore all possible paths level by level.
Example: Consider the same graph represented in Figure 4.13, as a tree with numeric nodes:
Here's how the BFS algorithm uses a queue to traverse this graph:
- Start with an empty queue and enqueue the root node (1).
- Step 1: Dequeue node 1 and mark it as visited. Enqueue all of its unvisited children (nodes 2, 3, 4). The queue now contains nodes [2, 3, 4],
- Step 2: Dequeue the front of the queue (node 2). Mark node 2 as visited and enqueue its unvisited children (nodes 5, 6). The queue now contains nodes [3, 4, 5, 6],
- Step 3: Dequeue the front of the queue (node 3). Mark node 3 as visited and enqueue its unvisited child (node 7). The queue now contains nodes [4, 5, 6, 7],
- Step 4: Dequeue the front of the queue (node 4). Mark node 4 as visited and enqueue its unvisited children (nodes 8, 9). The queue now contains nodes [5, 6, 7. 8, 9],