Breadth-first search and its uses

In the introductory tutorial, you played with having a character move through a maze to reach a goal. You started by saying that the goal is zero steps away from itself. Then you found all the squares that were one step away from the goal. Then all squares two steps away from the goal. Then three steps, and so on, until you reached the square where the character started. If you kept track of which square at distance $k$k you came from to get to a square at distance $k+1$k, plus, 1, you could backtrack to find a route from the character to the goal.

Here's the picture that we saw in the introductory tutorial:

Now you can recognize it as an undirected graph. Each vertex corresponds to a square that is not part of a wall, and each edge is incident on adjacent squares.

The route found by the above procedure has an important property: no other route from the character to the goal goes through fewer squares. That's because we used an algorithm known as breadth-first search to find it. Breadth-first search, also known as BFS, finds shortest paths from a given source vertex to all other vertices, in terms of the number of edges in the paths.

Here's another example of breadth-first search: the "six degrees of Kevin Bacon" game. Here, players try to connect movie actors and actresses to Kevin Bacon according to a chain of who appeared with whom in a movie. The shorter the chain, the better, and it's astounding how many actors and actresses can get to Kevin Bacon in a chain of six or fewer. As an example, take Kate Bell, an Australian actress. She was in MacBeth with Nash Edgerton in 2006; Edgerton was in The Matrix Reloaded with Laurence Fishburne in 2003; and Fishburne was in Mystic River with Kevin Bacon in 2003. Therefore, Kate Bell's "Kevin Bacon number" is 3. In fact, there are several ways to find that Kate Bell's Kevin Bacon number is 3. You can look up any actor's or actress's Kevin Bacon number at the Oracle of Bacon website.

As you might have guessed, the Oracle of Bacon website maintains an undirected graph in which each vertex corresponds to an actor or actress, and if two people appeared in the same film, then there is an edge incident on their vertices. A breadth-first search from the vertex for Kevin Bacon finds the shortest chain to all other actors and actresses.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.