# 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).