BFS vs DFS
Two ways to explore a graph. One of them finds the shortest route for free, and that's the one Fly-in needs.
1 · The problem
You stand at start and want to reach goal. You only know each zone's neighbours (that's network.neighbours). You can't see the whole map at once, so you have to explore: visit a zone, look at its neighbours, decide which to visit next.
BFS and DFS are the two classic answers to "which zone do I look at next?". That's literally the only difference between them.
"Closest first." Like a stone dropped in water: the ripple reaches everything 1 step away, then everything 2 steps away, then 3…
It uses a queue (a line at the bakery): first in, first out.
"Deepest first." Like walking a maze: pick a corridor and follow it to the end. Dead end? Walk back to the last fork and try the next one.
It uses a stack (a pile of plates): last in, first out.
2 · Watch them run
Same graph, same code, same neighbour order. Press Step and compare. S is start, G is goal. The short way is S → B → G (2 moves); the long way is S → A → C → D → G (4 moves).
S → B → G (2 moves, the shortest). DFS returns S → A → C → D → G (4 moves). DFS happily takes the first corridor it finds and never looks back to check whether there was something shorter.3 · BFS in code
A plain dict as the graph so it stays simple. came_from does two jobs: it remembers where each zone was reached from (to rebuild the route), and it doubles as the "already seen" set.
graph = {
"S": ["B", "A"],
"A": ["S", "C"],
"B": ["S", "G"],
"C": ["A", "D"],
"D": ["C", "G"],
"G": ["B", "D"],
}
def bfs(graph, start, goal):
queue = [start]
came_from = {start: None} # start has no parent
while queue:
zone = queue.pop(0) # take the OLDEST: first in, first out
if zone == goal:
return build_path(came_from, goal)
for nxt in graph[zone]:
if nxt not in came_from: # never visit a zone twice
came_from[nxt] = zone # "I reached nxt from zone"
queue.append(nxt)
return None # queue empty: goal unreachable
def build_path(came_from, goal):
path = []
zone = goal
while zone is not None: # walk back: G → B → S → None
path.append(zone)
zone = came_from[zone]
return path[::-1] # reverse: S → B → G
print(bfs(graph, "S", "G")) # ['S', 'B', 'G']Walking back through came_from
When BFS reaches G, came_from looks like this:
{"S": None, "B": "S", "A": "S", "G": "B", "C": "A"}Start at G and follow the arrows: G came from B, B came from S, S came from None → stop. That gives [G, B, S]; reversed, it's the route.
4 · DFS in code
Here's the surprise: it's the same function. Only one call changes.
def dfs(graph, start, goal):
stack = [start]
came_from = {start: None}
while stack:
zone = stack.pop() # take the NEWEST: last in, first out
if zone == goal:
return build_path(came_from, goal)
for nxt in graph[zone]:
if nxt not in came_from:
came_from[nxt] = zone
stack.append(nxt)
return None
print(dfs(graph, "S", "G")) # ['S', 'A', 'C', 'D', 'G']pop(0) vs pop() is the whole difference. Taking from the front means "the zone I discovered longest ago" → the closest ones go first → BFS. Taking from the back means "the zone I just discovered" → you keep diving deeper → DFS.You'll also see DFS written recursively. It does the same thing, with Python's call stack playing the role of the stack:
def dfs_recursive(graph, zone, goal, seen):
if zone == goal:
return [zone]
seen.add(zone)
for nxt in graph[zone]:
if nxt not in seen:
rest = dfs_recursive(graph, nxt, goal, seen)
if rest is not None:
return [zone] + rest
return None # dead end: go back
print(dfs_recursive(graph, "S", "G", set())) # ['S', 'B', 'G'] ← !B first. The stack version pushes B then A and pops A (the last one in) first. Same algorithm, different neighbour order, different answer. That's exactly the problem: DFS's result depends on order, never on distance. Change "S": ["B", "A"] to ["A", "B"] and the recursive one takes the long way too. BFS returns S → B → G either way.5 · Why BFS finds the shortest route
BFS works in layers. Everything at distance 1 leaves the queue before anything at distance 2, which leaves before anything at distance 3. So the first time it touches the goal, there can't be a shorter way, because all shorter distances were already fully checked.
DFS has no layers. It finds a route, and which one depends purely on neighbour order. Swap the order and you get a different answer. That's fine for "is there any way at all?", useless for "what's the fastest way?".
6 · Side by side
| BFS | DFS | |
|---|---|---|
| Next zone | the oldest discovered | the newest discovered |
| Data structure | queue (FIFO), pop(0) | stack (LIFO), pop() or recursion |
| Explores | in rings / layers | one branch to the end, then backtracks |
| Shortest route (in steps)? | ✅ guaranteed | ❌ any route |
| Finds the goal at all? | ✅ yes | ✅ yes |
| Memory | can hold a whole layer at once | only the current branch |
| Typical use | shortest path, "minimum number of moves" | maze generation, "is it connected?", trying all options |
| Where you met it | Network.is_reachable() | probably A-Maze-ing (the backtracker that carves the maze) |
7 · Why Fly-in needs BFS
A drone moves one zone per turn. So "fewest moves" = "fewest turns" = what the benchmarks score. That's exactly the question BFS answers. DFS could send a drone round a loop through half the map, and medium/02_circular_loop exists precisely to punish that.
Your is_reachable() already is a BFS. It just throws the route away. Add came_from + build_path and you have Pathfinder.shortest_path().
- Restricted zones cost 2 turns. Plain BFS counts moves, not turns, so a route through one restricted zone looks as cheap as a normal one. That's section 5's last item.
- Many drones. In section 6 the same BFS runs over
(zone, turn)pairs instead of just zones, so "wait one turn" becomes a move like any other. The skeleton you write now is the one you'll reuse.
list.pop(0) shifts every element, which is slow on big queues. collections.deque with popleft() does the same in constant time. It's standard library, not a graph library, so it's allowed.