Graph AlgosGraph Algorithms

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).

Learn 0-1 BFS →
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