Following our exploration of Depth-First Search, we now turn our attention to its equally important counterpart. In the last lesson, you learned how DFS plunges deep into a tree or graph using a stack (either implicitly via recursion or explicitly). Today, we will explore a different strategy: expanding our search wide, level by level.
This lesson introduces Breadth-First Search (BFS), a traversal algorithm that systematically explores a graph in layers. You will learn how its use of a queue enables this behavior, making it the perfect tool for specific problems that are common in technical interviews. We will focus on two key applications: performing a level-order traversal of a tree and, most importantly, finding the shortest path between two nodes in an unweighted graph.
1. The Essence of Breadth-First Search
Where DFS follows one path to its end before backtracking, BFS explores all of a node's immediate neighbors before moving on to the next layer. The classic analogy is the ripples spreading from a pebble dropped in a pond—each concentric circle represents a "level" of the search.
The key to this behavior is the data structure used to keep track of nodes to visit. While DFS uses a stack (Last-In, First-Out), BFS uses a queue (First-In, First-Out). When you discover a node's neighbors, you add them to the back of the queue. By always processing the node at the front of the queue, you ensure that you visit all nodes at depth d before moving on to any node at depth d+1.
The image below provides a great side-by-side comparison of the two traversal strategies on the same tree. Notice how BFS explores level by level (0 -> 1,2,3 -> 4,5,6,7), while DFS goes deep down one branch first (0 -> 1 -> 4 -> 5).
.png)
For a more theoretical overview, the article "Breadth-First Search (BFS) - Shortest Paths in Unweighted Graphs" from Interview Cake provides a solid foundation.
Breadth-First Search (BFS) - Shortest Paths in Unweighted ...
This section from Interview Cake explains the core ideas behind BFS, including the roles of the queue, a visited set, and a predecessor map.
Read the section Core Concepts. Pay close attention to the explanations for the three key data structures: The Queue: Why does a FIFO structure lead to level-by-level traversal? The Visited Hash Set: Why is this crucial for graphs that may contain cycles? The Predecessor Hash map: How does this allow us to reconstruct a path after the search is complete?
2. Implementing BFS in Go
Given your proficiency in Go, we'll dive into a practical implementation. The following article from reintech.io provides a clear, step-by-step guide to building a BFS algorithm from scratch, a common task in interviews. Since Go's standard library doesn't have a native queue type, you often start by implementing one.
Breadth-First Search Algorithm in Go
This article provides a complete, production-oriented guide to implementing BFS in Go, including a simple queue, the main algorithm, and a comparison with DFS.
Begin with the introduction, What Makes BFS Different?, to solidify your understanding of the algorithm's characteristics and complexity. Next, study the section Building a Queue in Go. While this slice-based queue is simple, note the performance consideration about the Dequeue operation. For the highly scalable systems you aim to build, being aware of such trade-offs is vital. The article's suggestion to use container/list for an O(1) queue is a key insight. Now, read through the core algorithm in Implementing BFS for Graph Traversal. Focus on the structure: initialize the queue and visited array, then loop until the queue is empty. Pay special attention to the author's note: you mark a node as visited when you enqueue it, not when you dequeue it. This prevents adding the same node to the queue multiple times. Finally, review the summary table in the section When to Use BFS vs. DFS. This is a classic interview question, so internalizing these trade-offs is essential.
3. Application 1: Binary Tree Level-Order Traversal
The most direct application of BFS to a tree structure is level-order traversal. This involves visiting all nodes at a given level from left to right before moving to the next level. This is exactly what BFS does naturally.
A common interview question (e.g., LeetCode 102) asks you to return the result as a list of lists, where each inner list contains the nodes of one level. To achieve this, you can use a clever trick within the main BFS loop: before processing a level, you record the current size of the queue. Then, you run an inner loop exactly that many times to process only the nodes belonging to the current level.
The following video from NeetCode provides an excellent walkthrough of this exact problem.
Binary Tree Level Order Traversal - BFS - Leetcode 102
This video breaks down LeetCode 102, "Binary Tree Level Order Traversal," explaining the BFS approach and the logic for grouping nodes by level.
Watch the introduction from the beginning to understand the problem statement. The presenter then identifies BFS as the correct algorithm and introduces the queue. Pay close attention to the walkthrough of the algorithm. The key is how he uses the queue's size at the start of each level's iteration to know how many nodes to process for that level's list. Finally, review the code implementation, which translates this logic directly into Python. The pattern is easily adaptable to Go.
4. Application 2: Shortest Path in Unweighted Graphs
This is arguably the most powerful and celebrated feature of BFS. In any unweighted graph (where every edge has the same cost or weight, i.e., 1), BFS is guaranteed to find the shortest path between a starting node and any other reachable node, measured by the number of edges.
Because BFS explores layer by layer, the first time it reaches a target node, it must have done so via a path with the minimum number of steps. If a shorter path existed, BFS would have found the target on an earlier level. This property is used everywhere, from finding the shortest number of connections between two people on a social network to solving maze puzzles.
To find the path itself, not just its length, we use the "predecessor map" or "parent array" concept mentioned earlier. As you traverse, whenever you visit a node V from a node U, you record that parent[V] = U. Once you reach the destination, you can reconstruct the path by backtracking from the destination to the start using this parent information.
William Fiset's video provides a great conceptual and animated explanation of this process.
Breadth First Search Algorithm Shortest Path Graph Theory
This video from WilliamFiset provides a thorough explanation of how BFS finds the shortest path, including animations and pseudocode for path reconstruction.
Watch the introduction to understand the core premise of BFS for shortest paths. The animated example is very helpful for visualizing the queue's operation and the layered exploration. Next, follow the pseudocode walkthrough. Focus on the roles of the visited array and the crucial prev array, which stores the parent pointers needed for path reconstruction. Finally, see how the path is built by backtracking from the end node using the prev array.
For a code-centric guide, the reintech.io article you reviewed earlier also contains an excellent section that adds path reconstruction to the Go implementation. I highly recommend studying this practical code.
Breadth-First Search Algorithm in Go
This section enhances the previous Go implementation to include logic for finding and reconstructing the shortest path.
Read the section Finding Shortest Path. Notice how the parent array is used to store the predecessor of each node during traversal. The path reconstruction logic at the end is a standard and efficient pattern for backtracking once the destination is found.
Conclusion
In this lesson, we contrasted the "go wide" strategy of Breadth-First Search with the "go deep" approach of DFS. You've seen how BFS's reliance on a queue naturally leads to a level-by-level exploration.
Key Takeaways:
- Core Mechanism: BFS uses a queue (FIFO) to explore nodes level by level, making it fundamentally different from the stack-based (LIFO) DFS.
- Level-Order Traversal: BFS is the natural algorithm for problems requiring you to process a tree or graph in layers, like the Binary Tree Level-Order Traversal interview problem.
- Shortest Path: For unweighted graphs, BFS is guaranteed to find the path with the fewest edges. This is one of its most critical applications in computer science.
- Path Reconstruction: By keeping track of each node's
parentorpredecessorduring traversal, you can efficiently reconstruct the shortest path after the search concludes.
In our next lesson, we will revisit Depth-First Search, but this time we'll apply it to more complex graph problems, such as finding all connected components and detecting cycles. This will further solidify your understanding of when to choose one traversal algorithm over the other.