Skip to content
BENIBIX Learn

Breadth-First Search (BFS)

Development🧮 Algorithms & Data StructuresSearch Algorithms

Also known as BFS, Breadth First Search, Level-Order Traversal

Walking a graph one layer at a time, nearest nodes first.

Think of it like

Think of it like ripples in a pond. They spread out one ring at a time.

Example

Emma's app finds how many steps away Jack is in her friend graph. BFS checks her friends, then theirs, and finds him at step 2.

Why it matters

It is the standard way to find the shortest path when every step costs the same.

Definition

Breadth-first search walks a graph or tree one layer at a time. It visits every neighbour of the start, then every neighbour of those, and so on. It keeps the nodes it has yet to visit in a queue. Because it goes layer by layer, it finds the path with the fewest steps first. It marks each node it has seen, so loops cannot trap it.

Common mistake

Forgetting to mark visited nodes. On a graph with loops, the search never ends.

Key takeaways

  1. 1
    Layer by layer. Nearest first.
  2. 2
    Uses a queue. First in, first out.
  3. 3
    Fewest steps. Found first.

Compare