Two BFS Approaches
- Pop One Element per Iteration
- Pop All Elements of the Current Level per Iteration (Level-by-Level approach).
Popping One Element per Iteration
- In each iteration of the while loop, you pop one node from the queue and process it.
- After processing that node (removing it and decrementing the in-degree of its neighbors), you append new leaves to the queue.
This method ensures that the queue is always dynamically adjusted as you process nodes one by one.
Why It Works:
- In a BFS, you’re exploring nodes in the order they were added, so popping one node at a time ensures you process the nodes in the correct order.
- You add newly found leaves (or neighbors) to the back of the queue, which guarantees they will be processed in the next “level” of the tree.
- The BFS traversal continues level by level even though you pop one element at a time, because the newly added nodes are processed after all nodes at the current level. Advantage: Simplicity. This approach is straightforward and easy to implement. It works well in most BFS scenarios without needing to explicitly manage levels.
Popping All Elements of the Current Level per Iteration (Level-by-Level Approach):
In this approach, each iteration of the while loop processes all nodes in the current level (i.e., all nodes that were added to the queue in the previous iteration). You can achieve this by first determining how many nodes are in the queue at the start of the iteration (level_size), then processing all those nodes before moving on to the next iteration.
Why It Works:
BFS guarantees that all nodes at the current level will be processed before moving to the next level, even if you append new nodes (leaves) during the current iteration. Because of how BFS handles the queue (FIFO—first in, first out), any nodes added during this iteration will be appended to the back of the queue and processed in the next iteration, maintaining the level-by-level order. This is effectively layered BFS, and it’s often used when you need to explicitly handle things by levels.