0-1 BFS
You'll learn how to find shortest paths in graphs where edges have weights of only 0 or 1 using a clever modification of standard BFS.
The Problem with Regular BFS
Standard BFS finds shortest paths in unweighted graphs (or equivalently, graphs where all edges have weight 1). But what if some edges have weight 0 and others weight 1? Regular BFS would fail because it assumes all neighbors are equally "far" from the current node.
The Core Idea
0-1 BFS uses a deque (double-ended queue) instead of a regular queue. The insertion strategy is simple but powerful:
- When you traverse an edge with weight 0, add the destination to the front of the deque
- When you traverse an edge with weight 1, add the destination to the back of the deque
Why This Works
Think of it like cutting in line: nodes reached via 0-weight edges are "just as close" as the current node, so they should be processed immediately (front insertion). Nodes reached via 1-weight edges are "one step farther," so they wait their turn (back insertion). This maintains the invariant that distances in the deque are non-decreasing.
Time Complexity
Like standard BFS, 0-1 BFS runs in O(V + E) time, where V is vertices and E is edges. Each vertex is processed once, and each edge is examined once. The deque operations (push front/back, pop front) are all O(1).
This is much faster than running Dijkstra's algorithm (which would be O(E log V) with a priority queue) for this special case!
Key Takeaway: 0-1 BFS efficiently finds shortest paths in graphs with only 0 and 1 edge weights by using a deque with a strategic insertion rule: weight-0 edges go to the front, weight-1 edges to the back.