Graph AlgosAlgorithmaka zero-one BFS, deque BFS

0-1 BFS

Shortest paths when every edge weighs 0 or 1: a deque replaces the heap — weight-0 edges push to the front, weight-1 edges to the back — giving O(V + E).

▶ VisualizePattern: Breadth-First SearchPractice (1)
Progress

Overview

0-1 BFS is Dijkstra's Algorithm specialised to graphs whose edge weights are only 0 or 1. Dijkstra needs a Priority Queue because distances popped must be non-decreasing. With only two weights you can keep the frontier sorted by hand: relaxing a weight-0 edge yields a node at the same distance, which belongs at the front of the Deque; a weight-1 edge yields a node at distance +1, which belongs at the back. No heap, no log factor.

Preconditions and complexity: weights ∈ {0, 1} (more generally {0, c}), directed or undirected, single source. O(V + E) time, O(V) space. Typical sources of 0/1 edges: grid moves that are free in one direction and cost 1 otherwise, "minimum number of obstacles to remove", "minimum edges to flip".

shortest pathdeque0/1 weightsO(V + E)

Intuition

A mental model before the formal terms.

You are handing out queue tickets in a hospital: patients who arrive with the same urgency as the one just called are let in immediately (front of the line), while everyone else joins the back. Because there are only two kinds of arrivals — "same as now" and "one worse" — the line stays sorted without ever needing to re-sort it.

How it works

  1. Set dist[s] = 0, others ∞; push s to the front of a deque.
  2. Pop from the front node u. For each edge u → v with weight w ∈ {0, 1}: if dist[u] + w < dist[v], update dist[v] and push v to the front if w == 0, else to the back.
  3. A node may be pushed more than once (its distance can improve from d + 1 to d); the stale copy is harmless because relaxation is monotone. Optionally skip a popped node whose stored distance is already smaller than the popped one.
  4. Repeat until the deque is empty. dist now holds shortest 0/1-weighted distances.

Why it works

Invariant (same as Breadth-First Search (BFS)): the deque always contains nodes with distances d, …, d, d+1, …, d+1 in that order. Popping a d node and pushing a d node to the front, or a d+1 node to the back, preserves the pattern. Therefore nodes are popped in non-decreasing distance order — exactly the property Dijkstra's correctness proof needs.

Each edge is relaxed a constant number of times (a node is popped at most twice: once with a stale distance, once with the final one), so total work is O(V + E).

Recognition

How to tell a problem wants this.

  • Edge costs are exactly two values, one of them 0: "moving along the belt is free, against it costs 1".
  • "Minimum number of obstacles / walls to remove to reach the target" — entering a wall cell costs 1, an empty cell 0.
  • "Minimum number of edges to reverse so a path exists" — original edges weigh 0, reversed copies weigh 1.
  • Dijkstra would work but constraints are tight (10^6 cells) and the log factor hurts.
“minimum steps” → Breadth-First Search“weighted graph” → Shortest Path (Weighted)

Interactive visualization

Play, step, change the input. ← → and space work too.

10101010111010A0B∞C∞D∞E∞F∞G∞H∞I∞J∞K∞L∞
Deque (front → back)
A
1/25Start at A. With weights only 0 and 1 a deque replaces the heap: weight-0 neighbors go to the front (same distance), weight-1 to the back (one more), so the deque stays sorted by distance.
Current nodeIn dequeProcessedWeight-0 edge (push front)Weight-1 edge (push back)
PseudocodeLearn 0-1 BFS →
1dist = {v: ∞}; dist[source] = 0; deque = [source]
2while deque not empty:
3  u = deque.popleft()
4  for (v, w) in neighbors(u):
5    if dist[u] + w < dist[v]:
6      dist[v] = dist[u] + w
7      if w == 0: deque.appendleft(v)
8      else: deque.append(v)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1dist = [INF] * n; dist[s] = 0; dq = deque([s])
2while dq:
3  u = dq.popleft()
4  for (v, w) in adj[u]:            # w in {0, 1}
5    if dist[u] + w < dist[v]:
6      dist[v] = dist[u] + w
7      if w == 0: dq.appendleft(v) else: dq.append(v)

Implementations

11 · Double-ended queue
2from collections import deque    # appendleft/popleft/append are all O(1)
3from math import inf
4 
5 
6def zero_one_bfs(adj: list[list[tuple[int, int]]], s: int) -> list[float]:
7    """adj[u] = [(v, w), ...] with w in {0, 1}; nodes 0..n-1.
8    Returns dist (inf = unreachable)."""
92 · Initialize distances
10    n = len(adj)
11    dist: list[float] = [inf] * n
12    dist[s] = 0
13    dq = deque([s])
143 · Pop from the front
15    while dq:
16        u = dq.popleft()
174 · Relax edges — weight 0 goes to the front, weight 1 to the back
18        for v, w in adj[u]:
19            if dist[u] + w < dist[v]:
20                dist[v] = dist[u] + w
21                if w == 0:
22                    dq.appendleft(v)
23                else:
24                    dq.append(v)
255 · Result
26    return dist
Walkthrough
  1. collections.deque natively supports appendleft — Python is the only one of the four languages where the algorithm needs zero scaffolding.
  2. Weight-0 neighbours go to the front (appendleft), weight-1 to the back (append).
  3. The relaxation test doubles as the visited check; re-pushed nodes are fine because dist only decreases.
  4. dist uses inf (a float) as the unreachable sentinel; reachable entries are exact ints.
Complexity (this implementation)
time O(V + E) · space O(V)

deque operations are O(1) at both ends; list.insert(0, v) would be O(n).

Language notes
  • deque is a doubly-linked list of blocks — appendleft never shifts elements.
  • A conditional expression (dq.appendleft if w == 0 else dq.append)(v) is a compact (if cheeky) alternative to the if/else.
  • For grid problems, iterate a delta table and compute w from the target cell instead of building adj.
Common mistakes in this language
  • Using list.insert(0, v) or list.pop(0) — both O(n).
  • Marking visited at enqueue time as in plain BFS — 0-1 BFS must allow re-relaxation.
  • Using this for weights {1, 2}: subtract nothing — one weight must be 0 (or split edges first).
Language differences that matter here
  • Deque availability: C++ std::deque and Python collections.deque are built in; JS/TS have neither, and unshift()/shift() are O(n) — hence the hand-rolled Map-based Deque (a ring buffer or two-stack pair also works).
  • The same JS/TS caveat from BFS applies doubly here: the algorithm pushes to both ends, so the head-index array trick alone is not enough.
  • Sentinels: C++ uses INT_MAX (safe because dist[u] + w is checked only when dist[u] is finite — a popped node is always finite); JS/TS Infinity and Python inf are arithmetic-safe regardless.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Each node is popped at most twice. Generalises to weights {0, c}; for weights in 0..K use Dial's algorithm (K+1 buckets) in O(E + V·K).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Edge weights are exactly 0 and 1 (or two values, one of them 0).
  • Grid problems: "minimum obstacles removed", "minimum direction changes", "cost 1 only when moving against the arrow".
  • Large graphs where Dijkstra's log V matters (10^6+ nodes).
Avoid it when

Alternatives

BFS Shortest Path (Unweighted)Dijkstra's AlgorithmBellman-Ford

Common mistakes

  • Marking nodes visited when first pushed — a node pushed to the back with d + 1 may later be reached with d and must be re-relaxed.
  • Pushing weight-0 neighbours to the back: the result is still correct in some graphs but not in general (breaks the sorted-deque invariant).
  • Using Array.shift()/unshift() in JavaScript for the deque — both are O(n).
  • Applying it to weights {1, 2} — must be {0, 1}; you can split a weight-2 edge into two weight-1 edges, but that changes the graph size.

Interview patterns

  • Minimum obstacle removal to reach a corner (entering an obstacle costs 1).
  • Minimum cost to make at least one valid path: following the cell's arrow costs 0, other moves cost 1.
  • Minimum edge reversals so s reaches t: add reversed edges with weight 1.
  • Bipartite-style layering where "same layer" moves are free.
Interview questions on this
Mock interviews

Example problems

Shortest Path in Binary Matrixmedium