0-1 BFS with a deque in Python

Why this matters

Plain breadth-first search (BFS) finds the route with the fewest hops, where every hop counts the same. Many real problems count moves unevenly. A ferry crossing might be free while a bus ride costs one ticket. A grid cell might be empty, which costs nothing to enter, or hold a wall you must break, which costs one. When each move costs either 0 or 1, you do not need the heavier method from the Dijkstra lesson in this module. A double-ended queue (a deque) is enough, and it runs in the same time as plain BFS.

The method has one idea at its core. You choose which end of the queue each new town goes to, and that choice keeps the queue in order of cost. The rest of this lesson shows why that works and how to write it in Python.

Words used in this lesson

• Cost: the number you pay to cross one edge. Here it is always 0 or 1.
• Distance: the smallest total cost from the start to a vertex. Distance is a sum of costs. Hops are a count of edges. The two are the same only when every cost is 1.
• Deque: a line of items where you can add and remove at both the front and the back. Python provides it as collections.deque.
• Relax: check whether the route through the current vertex is cheaper than the best route found so far to a neighbour. If it is, record the cheaper distance.
• Stale entry: a queue item whose recorded distance is older than the best distance now known for that vertex.
• Invariant: a rule that stays true after every step of the method. The proof in this lesson uses one.

The deque operations you need

A collections.deque also has pop(), which removes from the back. This lesson uses appendleft and popleft so each line says which end it touches.

math.inf is a float that is larger than every number. Adding a cost to it still gives math.inf, so the code does not need a special case for towns that have not been reached yet. Readers who know Java may expect Integer.MAX_VALUE here. math.inf plays the same role.

A small example first

Imagine six towns numbered 0 to 5. The roads have these costs:

• 0 to 1 costs 0 (a free tunnel)
• 0 to 2 costs 1
• 1 to 3 costs 1
• 2 to 3 costs 0 (a free ferry)
• 3 to 4 costs 1
• 2 to 4 costs 1
• 4 to 5 costs 0
• 1 to 5 costs 1

The question is: what is the lowest total cost to reach each town from town 0?

Plain BFS would count hops instead. From 0 to 5, the route 0, 1, 5 has two hops, so plain BFS says 2. But the first hop is a free tunnel, and the second hop costs 1. The real cost is 1. Plain BFS answers a different question.

Here is the method, step by step. The deque is written as a list from front to back. Each item is a pair of (town, distance).

Start with the deque [(0, 0)]. Town 0 has distance 0.

1. Take the front item, town 0 at distance 0.
   • Road 0 to 1 costs 0. Town 1 gets distance 0. The cost is free, so town 1 goes to the front. Deque: [(1, 0)].
   • Road 0 to 2 costs 1. Town 2 gets distance 1. It goes to the back. Deque: [(1, 0), (2, 1)].
2. Take town 1 at distance 0.
   • Road 1 to 0 gives nothing new.
   • Road 1 to 3 costs 1. Town 3 gets distance 1 and goes to the back. Deque: [(2, 1), (3, 1)].
   • Road 1 to 5 costs 1. Town 5 gets distance 1 and goes to the back. Deque: [(2, 1), (3, 1), (5, 1)].
3. Take town 2 at distance 1.
   • Road 2 to 3 costs 0. The new distance would be 1, which is not lower than the 1 already recorded for town 3. Nothing changes.
   • Road 2 to 4 costs 1. Town 4 gets distance 2 and goes to the back. Deque: [(3, 1), (5, 1), (4, 2)].
4. Take town 3 at distance 1. Its roads lead to 1, 2 and 4. The route to 4 would cost 2, which is not lower than 2. Nothing changes. Deque: [(5, 1), (4, 2)].
5. Take town 5 at distance 1.
   • Road 5 to 4 costs 0. The new distance for town 4 is 1, which is lower than the 2 recorded. Town 4 gets distance 1. The cost is free, so town 4 goes to the front. Deque: [(4, 1), (4, 2)].
6. Take town 4 at distance 1. None of its roads lowers a distance. Deque: [(4, 2)].
7. Take the item (4, 2). The distance recorded in this item is 2, but town 4 now has distance 1. The item is stale, so skip it.

The deque is empty. The distances are 0, 0, 1, 1, 1, 1 for towns 0 to 5. Step 5 is the important one. Town 4 was first put at the back with distance 2. A free road later found a route with distance 1. Because the road was free, town 4 went to the front and was handled before anything else. The old item at the back became stale and was skipped.

The rule in three lines

The method only needs these rules:

1. When an edge costs 0, add the neighbour to the front of the deque.
2. When an edge costs 1, add the neighbour to the back of the deque.
3. Add a neighbour only when the new distance is strictly lower than the distance already recorded for it.

Take items from the front. If an item is stale, skip it.

The complete Python program

This program builds the six-town map and prints the distances. It also prints the plain BFS hop counts, so you can compare the two answers.

Run it with:

python3 zero_one_bfs.py

The output is:

0-1 BFS cost from 0: [0, 0, 1, 1, 1, 1]
Plain BFS hops from 0: [0, 1, 1, 2, 2, 2]

The two lines differ for towns 1, 3, 4 and 5. The cost answer is the one the problem asks for when roads are free or cost one ticket.

Each graph entry is a list of (neighbour, cost) tuples. graph[u] is the list of roads leaving town u. The queue holds (town, distance) tuples, and d_u is the distance that was recorded for u when the item was added.

The check d_u > dist[u] is the stale check from step 7. A stale item holds an old distance. The vertex it names has already been handled with a better distance, so the item is skipped.

Why the method is correct

Two facts make the method work. Each has a short proof.

Fact 1: the deque stays in order

Read the deque from front to back. The distances never go down, and the first and last distances differ by at most 1.

This holds at the start, because the deque has one item. Now look at one step. The front item has the smallest distance in the deque. Call that distance d. Because the deque is in order and its distances differ by at most 1, every item has distance d or d + 1.

There are only two kinds of push:

• A free edge from the front item gives distance d. It goes to the front. d is still the smallest value, so the order holds.
• A cost 1 edge gives distance d + 1. It goes to the back. Every item is at most d + 1, so the order holds.

After each push, every item still has a distance of d or d + 1. The next step starts from the same kind of state, so the rule holds for the whole run.

This is also why a free edge must go to the front. If a distance d item went to the back, it would sit behind items with distance d + 1. The order would break, and the next fact would no longer hold.

Fact 2: a vertex taken from the front has its final distance

Suppose the algorithm takes vertex u from the front with distance d, but a cheaper route to u exists with total cost D, where D is less than d.

Walk along that cheaper route from the start. Look for the first vertex on the route that has not yet been handled with a distance of D or less. Call it y. Its predecessor on the route, x, was handled earlier with a distance of at most D. When x was handled, the algorithm relaxed the edge from x to y. Either that set y's distance to at most D and created an item for it, or y already had a distance of at most D and an item was already waiting. Either way, the deque holds an item for y with a distance of at most D.

That item is less than d. But u sat at the front with distance d, and the front holds the smallest distance in the deque. So the item for y should have been taken first. This is a contradiction, so no cheaper route exists.

The proof uses two conditions. Costs cannot be negative, so a route cannot get cheaper by adding more edges. And every cost is 0 or 1, so every new distance is d or d + 1, which is what keeps the deque in order.

Worked example 2: breaking walls on a grid

A grid is a graph too. Each cell is a vertex, and each cell touches the cells above, below, left and right of it. Here is a grid where 0 means an empty cell and 1 means a wall. You start at the top-left cell and want to reach the bottom-right cell. You may move up, down, left or right. Entering an empty cell costs 0. Entering a wall costs 1, because you must break the wall first. The question is: what is the fewest walls you must break?

0 1 1
1 1 0
1 1 0

The answer is 2. The route along the top row enters two walls, at the top middle and top right. It then goes down through two empty cells. The total cost is 2. The route down the left side enters three walls, so it costs 3.

Here is the Python program. The grid is the graph, so the cost of entering a cell is simply the value stored in that cell.

The output is:

Example 1: 2
Example 2: 0

The second grid has answer 0. A route with no walls exists. It goes down the left column, then along the bottom row to the middle column, up the middle column, across the top row, and down the right column to the bottom-right cell.

The cell (0, 0) is empty, so the code starts it at distance 0 without checking its value. The lists DR and DC hold the four moves as row and column changes. The bounds check stops the loop from stepping outside the grid. The check is needed in Python too, because grid[-1] does not raise an error. It wraps around to the last row.

Worked example 3: many starting points

The third example adds one change. Instead of one start, there are several exits. Each exit is a starting point at distance 0. The question is: how costly is it to reach each cell from its nearest exit?

The fix is small. Put all the exits into the deque at the start, before the loop begins. Everything else stays the same, because the method never cares where the distance-0 items came from. The program below is the grid program with that change:

Here is a grid with exits at the top-left and bottom-right cells. The exit cells are not charged. The other cells cost their own value to enter. The program prints this matrix:

[0, 0, 1, 1]
[1, 0, 1, 0]
[1, 0, 0, 0]

Check one cell by hand. The cell in row 0, column 3 has value 1. Its neighbour below, in row 1, column 3, has value 0 and sits next to the exit at row 2, column 3, so its distance is 0. Adding the cost of 1 for the top-right cell gives 1. The matrix agrees.

Common mistakes

Marking a vertex as done when it is first queued

A common version of BFS marks a vertex as seen the first time it is queued. That is correct for plain BFS, where every edge costs the same. With 0 and 1 costs it gives wrong answers. Here is a small graph with three towns. Road 0 to 1 costs 1. Road 0 to 2 costs 0. Road 2 to 1 costs 0.

def buggy_mark_on_push(graph, source):
    dist = [math.inf] * len(graph)
    dist[source] = 0
    queue = deque([(source, 0)])
    while queue:
        u, _ = queue.popleft()
        for v, cost in graph[u]:
            if dist[v] == math.inf:
                dist[v] = dist[u] + cost
                if cost == 0:
                    queue.appendleft((v, dist[v]))
                else:
                    queue.append((v, dist[v]))
    return dist
 
 
tri = [[] for _ in range(3)]
add_edge(tri, 0, 1, 1)
add_edge(tri, 0, 2, 0)
add_edge(tri, 2, 1, 0)
print("Correct:", zero_one_bfs(tri, 0))
print("Buggy:  ", buggy_mark_on_push(tri, 0))

This block uses add_edge and zero_one_bfs from the complete program above. Running both versions gives:

Correct: [0, 0, 0]
Buggy:   [0, 1, 0]

The buggy version reaches town 1 first through the cost 1 road, and records distance 1. It never looks at town 1 again, so it misses the free route through town 2. The fix is the one the lesson uses: keep updating a vertex while a strictly lower distance can be found.

Calling popleft on an empty deque

popleft() raises an error when the deque is empty. A loop that does not check the deque first will fail on the first call after the deque empties. Python reports this:

IndexError: pop from an empty deque

The while queue: loop in the code above checks the deque before every popleft(). Keep that check. A deque is false when it is empty, so while queue: stops at the right time.

Using <= instead of <

The relax check must use a strict comparison. With candidate <= dist[v], a free loop of two towns keeps adding each other to the front forever. Each pop adds the other town again, so the loop never reaches an empty deque and never ends. With <, a vertex is added again only when its distance really drops, and that cannot happen forever. If you run the <= version by mistake, stop it with Ctrl+C.

Using the method on costs of 2 or more

The method works only because every new distance is d or d + 1. A cost 2 edge gives d + 2, which can be two steps above the front. The back of the deque may already hold items with distance d + 1, so the order from Fact 1 breaks. The proof no longer holds, and the answer is not guaranteed. For costs of any non-negative size, use Dijkstra's algorithm with a priority queue. Python's heapq module provides the priority queue, and the Dijkstra lesson in this module covers it.

Practice

Exercise 1: trace the method

The graph has four vertices and these edges: 0 to 1 costs 1, 1 to 2 costs 0, 0 to 2 costs 1, and 2 to 3 costs 1. Find the distance from vertex 0 to each vertex. Trace the deque step by step.

Show the answer

The distances are [0, 1, 1, 2]. Vertex 1 is one costly step from 0. Vertex 2 is one costly step from 0, and the free road from 1 to 2 cannot make it cheaper than 1. Vertex 3 is one more costly step from vertex 2, so its distance is 2.

Exercise 2: why a free edge goes to the front

Explain in three or four plain sentences what would go wrong if a free edge put its neighbour at the back of the deque.

Show the answer

The neighbour would have the same distance as the front item, but it would wait behind items with distance d + 1. It would be handled after those items, which means its own free neighbours could be handled late too. The deque would no longer be in order, so the rule that the front holds the smallest distance would fail, and the proof in Fact 2 would no longer apply.

Exercise 3: small grids

Find the answer for each grid. Start at the top-left cell and reach the bottom-right cell. Entering an empty cell costs 0, and entering a wall costs 1.

Grid A        Grid B
0 1           0 0 0
1 0           1 1 0
              1 1 0

Show the answer

Grid A has answer 1. Both routes from the top-left cell cross one wall and then reach the bottom-right cell, which is empty. Grid B has answer 0. The top row is empty, and so is the right column, so you can walk from the top-left to the bottom-right without breaking any wall.

Exercise 4: is the stale check needed?

A teammate says the stale check (if d_u > dist[u]: continue) can be removed because the answers are the same. Is the teammate right about the answers? What does the check save?

Show the answer

The answers are the same without the check, because a stale item only holds an old, larger distance. Processing it again would try the same neighbours with the same candidate distances, so none of those updates would be accepted. The check saves that repeated work. On a large grid, many stale items can pile up, so the check can save a large amount of time.

Exercise 5: a loop of free roads

Take a triangle of three towns where every road costs 0. Does the method loop forever? Explain why.

Show the answer

No. A neighbour is added only when its new distance is strictly lower than its recorded distance. The first town starts at 0. The other two are reached at distance 0 and added once each. After that, every road would give distance 0, which is not lower than 0, so nothing else is added and the deque empties.

Summary

• A deque lets you add at both ends, so a 0-cost neighbour can go to the front and a 1-cost neighbour to the back.
• The deque always holds distances d and d + 1 in order, which makes the front item's distance final when it is taken.
• A vertex is added only when its distance strictly drops. Items that no longer match the best distance are skipped.
• Use the method for grids and graphs with costs of 0 or 1. For any other costs, use Dijkstra's algorithm.