Step 2. Breadth-first search

This program illustrates Breadth-first search. It is based on "Six Degrees of Kevin Bacon", which is the idea that most of Hollywood has either been in a movie with Kevin Bacon or in a movie with someone who was in a movie with Kevin Bacon, and so on.



Breadth-first se...
Breadth-first search for "Six Degrees of Kevin Bacon".


  • The program uses some movie data to show how an algorithm would search through a search tree, looking for a path to the goal (here, a path to Kevin Bacon).
  • It uses this movie data (JSON format). Note Kevin Bacon is in the first 3 movies but not in the last 2.
  • View console to see what is happening.


Look at the code

  • As with all Worlds on Ancient Brain, you can see the source code and clone it and edit it.
  • In the code you can see that the search starts with the start node, searches all neighbours, before those 2 steps away, before those 3 steps away, and so on. When it exits with goal node, it will have found a (joint) shortest route.
  • The FIFO queue is done with a JavaScript array and push and shift.


  1. Clone the World and Edit the code.
  2. Fix a bug: The search adds new nodes to the queue if they are not searched. But they might be on the queue already, just not searched. A node can be added multiple times to the queue. Search for "Michael Cyril Creighton" to see this. Edit the code and fix the bug.

  3. Another exercise: It would be faster if it checked for the goal node when adding new nodes to the queue. Do not add goal to queue. Just exit.
  4. Highlight the movie titles different to the actor names.
  5. What if no path found?
Tweet this step: