📈Graph Theory·15 min·Sample Lesson

Exploring a Maze Layer by Layer: Breadth-First Search

Imagine you drop a pebble into a still pond. The ripples spread out in perfect rings -- first a small circle, then a bigger one, then a bigger one still, always growing outward evenly in every direction at once. Computer scientists use that exact idea to explore mazes, find the fastest route on a map, and even figure out how many 'friends of friends' connect two people on a social network. It's called Breadth-First Search, or BFS for short.

What You'll Learn

- What a graph is: dots (nodes) connected by lines (edges) - How Breadth-First Search explores a graph one ring at a time - Why BFS always finds the SHORTEST path first - How to trace BFS by hand on a simple map

What Is a Graph?

In graph theory, a graph is just dots connected by lines. The dots are called nodes (they could be cities, friends, or rooms in a maze), and the lines are called edges (they show a connection, like a road between two cities). A map of subway stations connected by train lines is a perfect real-world graph.

How BFS Explores, Ring by Ring

BFS starts at one node and explores in layers, just like the pond ripples. Layer 0 is the starting node itself. Layer 1 is every node directly connected to the start. Layer 2 is every new node connected to a Layer 1 node. BFS finishes visiting an ENTIRE layer before moving to the next one -- it never jumps ahead to explore a distant node while a closer one is still unvisited. To keep track of what to visit next, BFS uses a line-up system called a queue: whichever node got added first gets explored first (just like the first person in line at a lunch line gets served first).

Why BFS Finds the Shortest Path

Because BFS visits every node exactly one step away before any node two steps away, the very first time it reaches your destination, that path is guaranteed to use the fewest possible edges. This is why video games use BFS-style algorithms to find the shortest route for a character to reach a target on a grid map, and why some GPS-style pathfinding starts with this same layer-by-layer idea.

BFS vs. DFS

BFS's cousin is Depth-First Search (DFS), which instead dives as deep as possible down ONE path before backtracking -- like exploring one hallway all the way to its end before trying a different hallway. DFS does not guarantee the shortest path; BFS does, because BFS always finishes closer layers first.

Let's trace it by hand. Picture 5 rooms in a house: Start, A, B, C, and Goal. Start connects to A and B. A connects to C. B connects to Goal. Using BFS: Layer 0 = Start. Layer 1 = A, B (both directly connected to Start). Layer 2 = C (from A), Goal (from B). BFS reaches Goal in Layer 2, meaning the shortest path is Start to B to Goal -- just 2 steps, even though A also looked like a promising direction.

Match each term to its correct meaning in graph theory.

Terms

Node

Edge

Queue

Layer

Definitions

A line showing a connection between two nodes

A dot representing a place, person, or item

A line-up where the first item added is the first one explored

All nodes the same number of steps from the start

Drag terms onto their definitions, or click a term then click a definition to match.

❓

Why does Breadth-First Search always find the shortest path between two nodes?

❓

In the 5-room example (Start, A, B, C, Goal), why does BFS find the path Start-B-Goal instead of going through A?

🎯

Trace BFS on Your Own Map

Draw 6 nodes labeled Start, A, B, C, D, Goal, and connect them with at least 6 edges of your choosing (make sure there's a path from Start to Goal). Then write out, layer by layer, the order BFS would visit each node, and circle the final shortest path from Start to Goal.

Want to keep learning?

Start Learning Free