Lesson 21.4 · Breadth-First Search
0-1 BFS with a Deque
When edges cost 0 or 1, push 0-cost neighbours to the front of a deque and 1-cost ones to the back. Nodes still come out in order of distance.
10 min
Think of it like this
Walking through a building where some doors are open (free) and others need a key (cost 1): you first explore everything reachable through open doors before using another key.
1.Why a deque works
BFS works because the queue holds distances d and d + 1 only, in order. With 0-cost edges, a neighbour has the same distance as the current node, so it belongs at the front; 1-cost neighbours go to the back. The deque stays sorted by distance, giving Dijkstra's answer in O(V + E) without a heap.
Because a node can be improved after it was first added, keep dist[] and only push when you find a smaller distance.
Remember
- Weight 0 → addFirst, weight 1 → addLast.
- Relax with dist[]; O(V + E).
- General non-negative weights need Dijkstra.
Common mistakes
- Using a visited-on-enqueue array (a 0-edge can improve a node later).