Breadth-first search

Breadth-first search is a search algorithm that runs on Graphs.^[1]

Breadth-first search, also known as “BFS”, is useful for pathfinding. Specifically, BFS allows us to determine whether a path exists from node A to node B and then find the shortest path from node A to node B on the graph.

What is “breadth-first” search?

The “breadth-first” aspect of this graph search algorithm involves prioritizing “first-degree” connections, followed by “second-degree” connections, followed by third, fourth, fifth, etc.

Imagine you need to search among your friends for someone who wears a red hat. If none of your immediate friends wears a red hat, expand the search to friends of your immediate friends. Then, to friends of your immediate friends’ friends, and so on until your search is complete.

Breadth-first search contrasts with Depth-first search, which involves drilling down through the connections of the first immediate connection before moving on to the second immediate connection.

Visual example

1 -- 2 -- 4 
 \
  3 -- 5 -- 7 
   \
    6 -- 8

In the above example, the nodes are numbered in an order they could be searched using BFS.

Another permutation of BFS on the same graph could look like this:

1 -- 3 -- 6 
 \
  2 -- 5 -- 8 
   \
    4 -- 7

Association with queues

Breadth-first search can be associated with Queue data structures, since the nodes in the graph are searched in the order they’re added (in the sense that “second-degree” nodes are added to the graph once “first-degree” nodes have been searched).

Implementation

Consider an example graph:

graph = {}
graph["chicago"] = ["detroit", "st. louis", "minneapolis"]
graph["detroit"] = ["chicago", "toronto"]
graph["st. louis"] = ["chicago, "nashville", "tulsa"]
graph["nashville"] = ["st. louis", "tulsa", "charlotte"]
graph["honolulu"] = []

Starting with “chicago”, we want to find “tulsa”. A breadth-first search would look like this:

search_queue = []
search_queue += graph["chicago"]
visited = []  # keep a "visited" list to prevent infinite loops

path_length = 0

while search_queue:
  city = search_queue.pop(0)
  
  if not city in visited:
    if city == "tulsa":
      print "Found!"
      return True
    else:
      search_queue += graph[city]
      visited.append(city)
      
  return False

Efficiency

Breadth-first search is O(V + E) (number of vertices + number of edges) in Big O notation. This is because the algorithm will potentially search all connections (number of edges) as well as potentially queueing all nodes in the graph (number of vertices).