How Breadth-First Search Works
Breadth-first search visits everything one hop away, then everything two hops away, using a queue. On an unweighted graph that makes the first path it finds the shortest one.
- A
Nothing yet.
- Not reached
- Waiting
- Current
- Finished
Start at A. Breadth-first keeps a queue, so nearer nodes come out first.
Counters
- Visited
- 0/8
- In the queue
- 1
- Nodes
- 8
- Edges
- 10
Settings
More options
Breadth-first
- 1
queue = [start]; seen = {start} - 2
while queue: - 3
node = queue.shift() - 4
for each neighbour: - 5
if neighbour not in seen: - 6
seen.add(neighbour) - 7
queue.push(neighbour)
What each one answers
| Algorithm | What it answers | Time | Needs |
|---|---|---|---|
| Breadth-first | Fewest hops from the start | O(V + E) | A queue |
| Depth-first | Reachability, one branch at a time | O(V + E) | A stack |
| Cycle detection | Does a cycle exist, and where | O(V + E) | Node colours |
| Topological sort | A valid order to do the work in | O(V + E) | No cycles |
| Dijkstra | Cheapest path by edge weight | O(E log V) | Non-negative weights |
Scroll the table sideways for the rest of the columns.
V is the number of nodes and E the number of edges. Switch to the graph with a cycle and the topological sort gets stuck: once a cycle exists there is no valid order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(V + E) | O(V + E) | O(V + E) | O(V) |
How breadth-first search works
Breadth-first search keeps a queue of vertices to explore. It takes one off the front, marks each unvisited neighbour as seen and pushes it onto the back, so the graph is explored in rings of increasing distance from the start. Because a vertex is reached for the first time on the shortest possible number of hops, recording each vertex's discoverer gives shortest paths on an unweighted graph for free.
- Mark the start as visited and put it in a queue.
- Take the vertex at the front of the queue.
- For each unvisited neighbour: mark it visited, record where it was reached from, and push it onto the back.
- Repeat until the queue is empty.
- Marking on enqueue, not on dequeue, is what stops a vertex being queued twice.
Implementation
from collections import deque
def bfs(graph, start):
visited = {start}
came_from = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbour in graph[node]:
if neighbour not in visited:
# Marked on enqueue, not on dequeue: otherwise a vertex with
# two discoverers gets queued twice.
visited.add(neighbour)
came_from[neighbour] = node
queue.append(neighbour)
return came_fromWhen to use it
- Use it for shortest paths on unweighted graphs: social distance, fewest moves in a puzzle, shortest route on a grid.
- Use it when the answer is probably close to the start: BFS finds it after exploring only the nearby part of the graph, where DFS might descend a long branch first.
- Use it to find connected components, to test bipartiteness, and as the traversal inside maximum-flow algorithms.
- Avoid it on graphs with weighted edges. Fewest hops is not cheapest path, and that is Dijkstra's job.