---
title: "BFS: Looking wide before looking deep: Bfs Looking Wide Before Looking Deep"
id: "14048"
type: "page"
slug: "01-bfs-looking-wide-before-looking-deep"
published_at: "2026-07-19T20:07:43+00:00"
modified_at: "2026-07-19T20:07:45+00:00"
url: "https://preppers-paradise.com/library/grokkingaialgorithmssecondedition/01-bfs-looking-wide-before-looking-deep/"
markdown_url: "https://preppers-paradise.com/library/grokkingaialgorithmssecondedition/01-bfs-looking-wide-before-looking-deep.md"
excerpt: "This section introduces the Breadth-First Search (BFS) algorithm, explaining how it systematically explores trees and graphs by visiting all nodes at a given depth before proceeding to the next level."
taxonomy_category:
  - "AI & Machine Learning"
  - "Books"
  - "Free Teaser"
taxonomy_post_tag:
  - "algorithms"
  - "bfs"
  - "breadth-first search"
  - "computer science"
  - "data structures"
  - "graph traversal"
  - "maze solving"
  - "pathfinding"
  - "python"
  - "tree traversal"
---

# BFS: Looking wide before looking deep: Bfs Looking Wide Before Looking Deep

[← BFS: Looking wide before looking deep](/library/grokkingaialgorithmssecondedition/)

Chapter 1 of 80 · Free teaser

# BFS: Looking wide before looking deep

Now that we understand the ideas behind trees and the maze example, let's explore how search algorithms can generate trees that seek out paths to the goal. Breadth-first search (BFS) is an algorithm used to traverse or generate a tree. This algorithm starts at a specific node, usually the root, and explores every node at that depth before exploring the next depth of nodes. Think of BFS as being like dropping a stone into a calm pond. The ripples expand uniformly in all directions, touching everything 1 meter away, then everything 2 meters away, and so on. The algorithm mimics this expanding ring, visiting all neighbors at the current depth before moving outward. This guarantees that the shortest path in unweighted graphs (graphs in which all edges have the same cost) is found.

The BFS algorithm is best implemented by using a first-in, first-out (FIFO) queue in which the current depths of nodes are processed and their children are queued to be processed later. This order of processing is exactly what we require when implementing this algorithm. Figure 2.16 is a flow chart describing the sequence of steps involved in the algorithm.

![Flow of the BFS algorithm](https://preppers-paradise.com/wp-content/uploads/x402-books/grokkingaialgorithmssecondedition/_page_72_Figure_2.jpeg)
**Figure 2.16 Flow of the BFS algorithm**

### Steps of the BFS algorithm

Let's walk through each step in the algorithm to learn exactly what operations happen:

1.  *Enqueue root node.* The BFS algorithm is best implemented with a queue. Objects are processed in the sequence in which they are added to the queue. This process is known as FIFO. The first step is adding the root node to the queue. This node represents the starting position of the player on the map.
2.  *Mark the root node as visited.* Now that the root node has been added to the queue for processing, it is marked as visited to prevent it from being revisited for no reason.
3.  *Is the queue empty?* If the queue is empty (all nodes have been processed after many iterations), and if no path has been returned in step 12 of the algorithm, there is no path to the goal. If there are still nodes in the queue, the algorithm can continue its search for the goal.
4.  *Return* No path to goal. This message is the one possible exit from the algorithm if no path to the goal exists.
5.  *Dequeue the node as the current node.* By pulling the next object from the queue and setting it as the current node of interest, we can explore its possibilities. When the algorithm starts, the current node will be the root node.
6.  *Get the next neighbor of the current node.* This step involves getting the next possible move in the maze from the current position by referencing the maze and determining whether north, south, east, or west movement is possible.
7.  *Is the neighbor visited?* If the current neighbor hasn't been visited, it hasn't been explored yet and can be processed now.
8.  *Mark the neighbor as visited.* This step indicates that this neighbor node has been visited.
9.  *Set the current node as the parent of the neighbor.* This step is important for tracing the path from the current neighbor to the root node. From a map perspective, the *origin* is the position the player moved from, and the *current neighbor* is the position the player moved to.
10. *Enqueue the neighbor.* The neighbor node is queued for its children to be explored later. This queuing mechanism allows nodes from each depth to be processed in that order.
11. *Is the goal reached?* This step determines whether the current neighbor contains the goal that the algorithm is searching for.
12. *Return the path using the neighbor.* By referencing the parent of the neighbor node, then the parent of that node, and so on, the path from the goal to the root is described. The root node will be a node without a parent.
13. *Does the current node have a next neighbor?* If the current node has more possible moves to make in the maze, jump to step 6 for that move.

Let's walk through what that process would look like in a simple tree. As the tree is explored and nodes are added to the FIFO queue, the nodes are processed in the desired order by using the queue (figures 2.17 and 2.18).

![The sequence of tree processing using BFS (part 1)](https://preppers-paradise.com/wp-content/uploads/x402-books/grokkingaialgorithmssecondedition/_page_74_Figure_2.jpeg)
**Figure 2.17 The sequence of tree processing using BFS (part 1)**

![The sequence of tree processing using BFS (part 2)](https://preppers-paradise.com/wp-content/uploads/x402-books/grokkingaialgorithmssecondedition/_page_75_Figure_2.jpeg)
**Figure 2.18 The sequence of tree processing using BFS (part 2)**

### Exercise: Determine the path to the solution

What would be the order of visits using BFS for the following tree?

![Exercise tree diagram](https://preppers-paradise.com/wp-content/uploads/x402-books/grokkingaialgorithmssecondedition/_page_76_Figure_4.jpeg)

Solution:

![Solution for exercise tree diagram](https://preppers-paradise.com/wp-content/uploads/x402-books/grokkingaialgorithmssecondedition/_page_76_Figure_6.jpeg)

In the maze example, the algorithm needs to understand the current position of the player in the maze, evaluate all possible choices for movement, and repeat that logic for each choice of movement made until the goal is reached. By doing so, the algorithm generates a tree with a single path to the goal.

It's important to understand that the process of visiting nodes in a tree generates nodes in a tree. We're simply finding related nodes through a mechanism.

Each path to the goal consists of a series of moves to reach the goal. The number of moves in the path is the distance to reach the goal for that path, which we'll call the *cost*. The number of moves also equals the number of nodes visited in the path, from the root node to the leaf node that contains the goal. The algorithm moves down the tree depth by depth until it finds a goal; then it returns the first path that got it to the goal as the solution. A more optimal path to the goal may exist, but because BFS is uninformed, it isn't guaranteed to find that path.

**NOTE** In the maze example, all search algorithms used terminate when they find a solution to the goal. It's possible to allow these algorithms to find multiple solutions with a small tweak to each algorithm, but the best use cases for search algorithms find a single goal because it's often too expensive to explore the entire tree of possibilities.

Figure 2.19 shows the generation of a tree using movements in the maze. The BFS algorithm has explored up to depth 5 of the tree. On the actual map, two paths to the goal emerge from the search thus far.

![Maze movement tree generation using BFS](https://preppers-paradise.com/wp-content/uploads/x402-books/grokkingaialgorithmssecondedition/_page_78_Figure_2.jpeg)
**Figure 2.19 Maze movement tree generation using BFS**

Because the tree is generated with BFS, the algorithm generates each depth to completion before looking at the next depth. Figure 2.20 illustrates the entire tree of possibilities (shown only for learning purposes). At depth 7, BFS found a path to the goal, so our solution is south, south, west, west, north, north, north.

![Nodes visited in the entire tree after BFS](https://preppers-paradise.com/wp-content/uploads/x402-books/grokkingaialgorithmssecondedition/_page_79_Picture_3.jpeg)
**Figure 2.20 Nodes visited in the entire tree after BFS**

#### Python code sample of the BFS algorithm

As mentioned earlier, the BFS algorithm uses a queue to generate a tree one depth at a time. Having a structure to store visited nodes is critical to prevent getting stuck in cyclic loops, and setting the parent of each node is important for determining a path from the starting point in the maze to the goal:

```python
from collections import deque

def run_bfs(maze_puzzle, current_point, visited_points):
    queue = deque()
    queue.append(current_point)
    visited_points.append(current_point)
    while queue:
        current_point = queue.popleft()
        neighbors = maze_puzzle.get_neighbors(current_point)
        for neighbor in neighbors:
            if not is_in_visited_points(neighbor, visited_points):
                neighbor.set_parent(current_point)
                queue.append(neighbor)
                visited_points.append(neighbor)
                if maze_puzzle.get_current_point_value(neighbor) == '*':
                    return neighbor
    return 'No path to the goal found.'
```