🎓 A1Learner
🔍

DSA 0-1 BFS

0-1 BFS finds shortest paths in a graph where every edge weight is only zero or one. A deque replaces the heap, because the next cheapest node always waits at an end.

Front for free, back for one

The appendleft call puts a node ahead of everyone already waiting. The append call leaves its node behind them all.

from collections import deque

dq = deque([3])
dq.appendleft(1)
print("after 0-edge push:", list(dq))
dq.append(5)
print("after 1-edge push:", list(dq))
print("front leaves first:", dq.popleft())

A zero edge jumps the queue

The zero edge to node 1 puts it ahead of node 2 in the deque. Node 1 leaves first, and its costly edge cannot improve node 2.

from collections import deque

graph = {0: [(1, 0), (2, 1)], 1: [(2, 1)], 2: []}
dist = {0: 0, 1: 99, 2: 99}
dq = deque([0])
while dq:
    u = dq.popleft()
    for v, w in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            if w == 0:
                dq.appendleft(v)
            else:
                dq.append(v)
    print("deque:", list(dq), "dist:", dist)

Why plain BFS fails

Breadth-first search counts edges rather than weights. Two free edges beat one costly edge on this tiny graph.

edges = [(0, 1, 1), (0, 2, 0), (2, 1, 0)]
best = {}
for u, v, w in edges:
    best[(u, v)] = w
print("plain BFS would pay 1 for 0 -> 1")
print("0-1 BFS pays:", best[(0, 2)] + best[(2, 1)], "via node 2")

Example

from collections import deque


def zero_one_bfs(n, graph, source):
    dist = [10 ** 9] * n
    dist[source] = 0
    dq = deque([source])
    pops = 0
    relaxations = 0
    while dq:
        u = dq.popleft()
        pops += 1
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                relaxations += 1
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
        print("after pop", u, "deque:", list(dq), "dist:", dist)
    return dist, pops, relaxations


graph = {
    0: [(2, 0), (3, 1)],
    1: [(4, 0)],
    2: [(1, 0)],
    3: [(4, 1)],
    4: [(5, 0)],
    5: [],
}
dist, pops, relaxations = zero_one_bfs(6, graph, 0)
print("distances from 0:", dist)
print("pops:", pops, "successful relaxations:", relaxations)

Key points

  • A deque is a double-ended queue with pushes and pops at both ends.
  • A zero edge sends its target to the front of the deque.
  • A one edge sends its target to the back of the deque.
  • Distances inside the deque never decrease from front to back.
  • That ordering makes the front node the cheapest unsettled node.

In this example, zero edges pull nodes 2, 1, 4 and 5 to the front of the deque in turn. Only the edge into node 3 costs anything, so node 3 alone ends with distance 1. Six pops and five successful relaxations settle all six distances.

Note

any weight beyond zero and one breaks the ordering, and a heap takes over again.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A relaxed edge has weight 0. Where does its target enter the deque?