Paul's Python CoursePPC

Breadth-first search

Not met yet

Breadth-first search explores a graph nearest first. Keep a queue: take the place at the front, and put each neighbour that hasn't been reached yet on the back, marking it as reached as you queue it. Everything one step away comes out before anything two steps away, so the first time BFS reaches a place, it has found the fewest steps there. Note where each place was reached from, and you can walk the route back from the goal. Each place is queued once, so it's O(places + roads).

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks breadth-first search follows one road as far as it goes before trying the next.
  • Thinks a place reached by two roads is queued and visited twice, even though it was marked as reached the first time it was queued.
  • Thinks the first route breadth-first search finds to a place might not be the one with the fewest roads.
  • Thinks it makes no difference whether a place is marked as reached when it's queued or when it's taken off the queue.

Where it comes up