Breadth-First Search (BFS) on a Graph
In the queue
- A
Visit order
Nothing yet.
- Not reached
- Waiting
- Current
- Finished
1/20
Start at A. Breadth-first keeps a queue, so nearer nodes come out first.
Settings
Graph
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 | Whether there is a cycle, 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. On the graph with a cycle, topological sort gets stuck, because a cycle leaves no valid order.