Blog Posts

Exploring Breadth First Search (BFS) Algorithm

December 24, 2025


We talked about Depth First Search (DFS) last time, the algorithm that dives deep into one path before backtracking. Let’s explore another way to navigate a graph, Breadth First Search (BFS).

If DFS is like exploring a maze by going as far as you can down one hallway until hitting the wall, BFS is more like exploring all paths at the same time. You start at the entrance, check out all the doors you can reach in one move, then explore the rooms behind those doors, and keep going outward. It is a step-by-step/layer-by-layer approach, which makes BFS great for finding the shortest path or figuring out how everything is connected.


 

What Is BFS? 

BFS is a method for visiting every node in a graph. It works by exploring all nearby nodes first,+ then gradually moving farther away. It explores everything close to the starting point before moving outward. Here is how it works:

  1. Start at your chosen node (the “source”).

  2. Visit it and mark it as visited so you don’t re peat it.

  3. Add it to a queue (a line where the first in is the first out).

  4. While the queue isn’t empty: Take the first node from the queue; then visit all its un-visited neighbors and add them to the queue.

  5. Keep going until everything reachable has been visited.


 

Example Problem

Let’s revisit the same coding challenge as an example: finding all possible paths from node 0 to node 5 where each path is strictly ascending.

 

The BFS traversal process is illustrated step-by-step below. Instead of enqueuing single nodes, we enqueue partial paths.

  • Step 1: Start at 0.

    • Neighbors of 0: 1, 2

    • Queue: [0,1], [0,2]

  • Step 2:Expand [0,1].

    • Neighbors of 1: 2, 3, 4

    • Queue: [0,2], [0,1,2], [0,1,3], [0,1,4]

  • Step 3:Expand [0,2].

    • Neighbors of 2: 3, 4

    • Queue: [0,1,2], [0,1,3], [0,1,4], [0,2,3], [0,2,4]

  • Step 4: Expand [0,1,2]

    • Neighbors of 2: 3, 4

    • Queue: [0,1,3], [0,1,4], [0,2,3], [0,2,4], [0,1,2,3], [0,1,2,4]

  • Step 5: Expand [0,1,3]

    • Neighbors of 3: 4, 5

    • [0,1,3,5]hits target →record

    • Queue: [0,1,4], [0,2,3], [0,2,4], [0,1,2,3], [0,1,2,4], [0,1,3,4]

  • Step 6: Expand [0,1,4]

    • Neighbors of 4: 5

    • [0,1,4,5]hits target →record

    • Queue: [0,2,3], [0,2,4], [0,1,2,3], [0,1,2,4], [0,1,3,4]

  • Step 7: Expand [0,2,3]

    • Neighbors of 3: 4, 5

    • [0,2,3,5]hits target →record

    • Queue: [0,2,4], [0,1,2,3], [0,1,2,4], [0,1,3,4], [0,2,3,4]

  • Step 8: Expand [0,2,4]

    • Neighbors of 4: 5

    • [0,2,4,5]hits target → record

    • Queue: [0,1,2,3], [0,1,2,4], [0,1,3,4], [0,2,3,4]

  • Step 8: Expand [0,1,2,3]

    • Neighbors of 3: 4, 5

    • [0,1,2,3,5]hits target →record

    • Queue: [0,1,2,4], [0,1,3,4], [0,2,3,4], [0,1,2,3,4]

  • Step 9: Expand [0,1,2,4]

    • Neighbors of 4: 5

    • [0,1,2,4,5]hits target →record

    • Queue: [0,1,3,4], [0,2,3,4], [0,1,2,3,4]

  • Step 10: Expand [0,1,3,4]

    • Neighbors of 4: 5

    • [0,1,3,4,5]hits target →record

    • Queue: [0,2,3,4], [0,1,2,3,4]

  • Step 10: Expand [0,2,3,4]

    • Neighbors of 4: 5

    • [0,2,3,4,5] hits target → record

    • Queue: [0,1,2,3,4]

  • Step 11: Expand [0,1,2,3,4]

    • Neighbors of 4: 5

    • [0,1,2,3,4,5] hits target → record

    • Queue empty  mission accomplished!

All BFS-discovered paths from 0 to 5 (shortest to longest) are summarized as follows:

  1. Length 3 (shortest): [0,1,3 ,5], [0,1,4 ,5], [0,2,3,5], [0,2,4,5]

  2. Length 4: [0,1,2 ,3 ,5], [0,1,2,4,5], [0,1,3,4,5], [0,2,3,4,5]

  3. Length 5 (longest): [0,1,2,3,4,5]

  4. There are 9 total paths from 0 to 5 in the strict ascending order.


 

Why BFS Matters?

It is obvious that BFS works quite differently from DFS. BFS guarantees the shortest path appears first because it expands by levels, while DFS may quickly reach the target but not necessarily via the shortest route. BFS is memory-intensive for large branching factors; DFS is stack-intensive for deep graphs.

BFS isn’t just a theoretical concept. It powers many systems in our daily life. For example,

  • Route Optimization in Maps and Games. BFS helps find the shortest path between locations, ensuring efficient navigation in GPS systems and game environments.

  • Web Crawlers. Search engines use BFS-like strategies to discover websites link by link, indexing pages layer by layer.

  • Social Network Analysis. BFS measures degrees of separation between people, enabling features like “friends of friends” and connection recommendations.

  • AI Pathfinding. Robots and puzzle-solving algorithms rely on BFS to navigate environments safely and efficiently.