Breadth First Search
Exploring in rings.
Breadth first search explores a graph in rings. First the starting node, then all its neighbours, then their neighbours, and so on. Like ripples spreading out in a pond. It's the same idea as level order in a tree, with one extra detail.

- Explore in rings
- Like ripples in a pond
- One extra detail
BFS with a visited set
The extra detail is a visited set. Graphs can have cycles, so without it, we'd go round in circles forever. We start from Ana. Each time we take someone from the front of the queue, we add any friends we haven't seen yet to the back. Run it. Ana's friends come first, then friends of friends.
from collections import deque
from graph import friends
def bfs(start):
visited, queue, order = {start}, deque([start]), []
while queue:
person = queue.popleft()
order.append(person)
for f in friends[person]:
if f not in visited:
visited.add(f)
queue.append(f)
return order
print(bfs("Ana"))['Ana', 'Ben', 'Cara', 'Dev', 'Eli', 'Fay']
Also uses graph.py
friends = {
"Ana": ["Ben", "Cara"],
"Ben": ["Ana", "Dev"],
"Cara": ["Ana", "Dev", "Eli"],
"Dev": ["Ben", "Cara", "Fay"],
"Eli": ["Cara"],
"Fay": ["Dev"],
}BFS facts
Breadth first search visits every node and every edge once, so it's O of V plus E, the number of nodes plus the number of edges. It always reaches nearer nodes before farther ones. That makes it perfect for finding the shortest path, when every edge counts the same.
| key | value |
|---|---|
| Uses | a queue + visited set |
| Order | nearest first |
| Cost | O(V + E) |
| Great for | shortest paths |
Summary
Breadth first search uses a queue and a visited set to explore a graph in rings, nearest first. Next, depth first search.
Key takeaways- Queue
- Visited set
- Nearest first