Algorithm Deep Dive: 0-1 BFS & Bidirectional Search

Origins and the Shared Idea

Breadth-first search is the natural shortest-path algorithm when every move has the same cost: its FIFO queue processes vertices one distance layer at a time. The two techniques in this article preserve that useful order while exploiting extra structure in the problem.

One principle, two different shortcuts

0-1 BFS Edge costs have only two levels, so a deque can imitate the relevant ordering of Dijkstra's priority queue.

Two-way
BFS Both endpoints are known, so two ordinary BFS waves can meet near the middle instead of one wave reaching all the way across.

The names sound related because both contain “BFS,” but they solve different kinds of problems. 0-1 BFS changes how vertices are ordered; bidirectional BFS changes where the exploration begins. They can even be combined, but the stopping condition then needs the same care as bidirectional Dijkstra.

Choose the Right Search

Costs are 0 or 1

Use 0-1 BFS for one source to one or many destinations. A 0-cost edge goes to the front; a 1-cost edge goes to the back.

weighted single source deque

One source, one target

Use bidirectional BFS when edges are unweighted and the target is known. Search from both ends and join the parent chains.

unweighted single pair two queues

Graph condition	Best starting point	Why
Every edge has equal cost	Ordinary BFS	A FIFO queue already gives distance order.
Every weight is exactly 0 or 1	0-1 BFS	A deque replaces the heap and keeps linear time.
Arbitrary non-negative weights	Dijkstra	A priority queue is needed to select the smallest tentative distance.
Unweighted, one known source-target pair	Bidirectional BFS	Two shallower searches often inspect far fewer vertices.

0-1 BFS: A Two-Level Priority Queue

Let each edge weight be $w \in \{0,1\}$. Relaxation is exactly the same as in Dijkstra's algorithm:

$$\text{if } dist[u] + w(u,v) < dist[v], \quad dist[v] \leftarrow dist[u] + w(u,v).$$

The specialization is in where the improved vertex goes. A 0-edge creates work at the current distance, so it belongs at the front. A 1-edge creates work for the next distance layer, so it belongs at the back.

A 0-edge keeps the same tentative distance and therefore cuts to the front. A 1-edge waits behind all work at the current distance.

Initialize distances.Set $dist[s]=0$, every other distance to infinity, and place only $s$ in the deque.

Take the closest pending vertex.Remove $u$ from the front. The deque ordering makes it the next useful distance label.

Relax every outgoing edge.If $dist[u]+w

Place the improvement by cost.Use appendleft(v) for $w=0$ and append(v) for $w=1$.

The invariant that replaces a heap

Suppose the vertex at the front has distance $d$. Every vertex already waiting in the deque has distance $d$ or $d+1$. Relaxing a 0-edge creates another $d$-vertex and places it before the $d+1$ group; relaxing a 1-edge creates a $d+1$-vertex and places it after the $d$ group.

That is exactly the amount of ordering this weight set needs. A general-purpose priority queue would work, but it would spend $O(\log V)$ time maintaining distinctions that can never occur.

Intuition: imagine an airport line. A 0-cost transfer keeps you inside the same terminal, so you continue immediately. A 1-cost transfer moves you to the next terminal, so it waits behind every route still inside the current one.

Bidirectional BFS: Meet Near the Middle

Bidirectional BFS applies to an unweighted source-to-target query. One BFS grows from $s$ and another grows from $t$. If the shortest path has $d$ edges and the local branching factor is roughly $b$, an idealized one-way search may expose about $b^d$ states, whereas two balanced searches expose roughly

$ 2b^{d/2}\quad\text{instead of}\quad b^d. $

This is a geometric intuition, not a better worst-case bound: either method can still visit the whole graph, so the graph-theoretic worst case remains $O(V+E)$.

The search does not need to “guess” the middle vertex. The first balanced layer intersection identifies a shortest join; the two parent maps then recover the route.

Seed both directions.Start one frontier at $s$ and one at $t$. Keep separate distance and parent maps.

Expand a complete layer.Discover all previously unseen neighbors on one side, then test whether any is already known by the other side.

Alternate directions.Keeping layer depths balanced makes the first intersection argument transparent. Production versions often expand the smaller frontier, but must preserve a correct lower-bound stopping rule.

Join at a meeting vertex.Follow forward parents back to $s$ and backward parents toward $t$.

Directed graphs need reverse edges

The search from $t$ must answer “which vertices can reach me?” For a directed graph, run that side over the transpose graph, where every edge is reversed. Reusing the forward adjacency list is correct only when the graph is undirected.

Worked Examples and Failure Intuition

0-1 BFS trace: why a permanent visited flag is dangerous

Use source 0 and directed edges $(0,1,1)$, $(0,2,0)$, $(2,3,0)$, and $(2,1,0)$. Vertex 1 first receives distance 1, but the later route $0\rightarrow2\rightarrow1$ costs 0.

Action	Successful relaxation	Deque after action	Known distances
Initialize	—	`[0]`	`d[0]=0`
Pop 0	$0\to1$ costs 1; $0\to2$ costs 0	`[2, 1]`	`d[2]=0, d[1]=1`
Pop 2	$2\to3$ costs 0; $2\to1$ improves 1 to 0	`[1, 3, 1]`	`d[1]=0, d[3]=0`
Pop 1	No improvement	`[3, 1]`	`d[1]=0` is final
Finish	The stale second copy of 1 changes nothing	`[]`	`[0, 0, 0, 0]`

Do not copy ordinary BFS's visited-on-enqueue rule

In ordinary BFS, the first discovery is shortest because every edge adds one. In 0-1 BFS, a vertex discovered through a 1-edge can later improve through zero-cost edges. Use the relaxation test against dist[v]; do not forbid a useful re-enqueue merely because $v$ was seen before.

Bidirectional trace: six edges become two depth-3 searches

For the path $S\!\to a\!\to b\!\to M\!\to c\!\to d\!\to T$, one-way BFS must reach depth 6. With alternating layers, the forward side knows $b$ at depth 2 and then $M$ at depth 3; the backward side similarly reaches $M$ at depth 3. The meeting distance is

$$dist_S[M] + dist_T[M] = 3 + 3 = 6.$$

The saving becomes dramatic when every vertex has many irrelevant neighbors: reducing the explored depth reduces the entire branching tree, not just the six vertices on the final path.

Path Reconstruction

Distances answer “how short?” Parent pointers answer “which route?” The two algorithms store them slightly differently.

0-1 BFS predecessor

Whenever an edge improves dist[v], set parent[v] = u. After the algorithm finishes, follow parents from the destination back to the source and reverse the list.

Update the parent only on a strict distance improvement, exactly where relaxation succeeds.

Two parent forests

parentFromStart[v] points toward $s$. parentToTarget[v] points toward $t$. At meeting vertex $m$, build $s\leadsto m$, then append the chain after $m$ toward $t$.

Include the meeting vertex once. Duplicating $m$ is the most common reconstruction bug.

Complexity Without the Hand-Waving

Algorithm	Worst-case time	Auxiliary space	Practical search volume	Requirement
0-1 BFS	$O(V+E)$	$O(V)$	Each successful label change schedules constant-time deque work.	Weights exactly in $\{0,1\}$
Ordinary BFS	$O(V+E)$	$O(V)$	Up to about $b^d$ states in a tree-like search.	Equal edge costs
Bidirectional BFS	$O(V+E)$	$O(V)$	Ideally about $2b^{d/2}$ states.	Unweighted, known target
Dijkstra with heap	$O((V+E)\log V)$	$O(V)$	Handles all non-negative weights.	Non-negative weights

The shortest mental model: 0-1 BFS is Dijkstra with only two possible priority levels; bidirectional BFS is ordinary BFS with two origins and a join.

Ask what structure the input guarantees before choosing either optimization.

Implementations

Each tab contains both algorithms. The 0-1 routine validates its weight contract; the bidirectional routine returns a path and accepts both the forward and reverse adjacency lists. For an undirected graph, those two lists are the same object.

from collections import deque

INF = float("inf")
UNSEEN = -2

def zero_one_bfs(n, adj, source):
    """Return shortest distances when every edge weight is 0 or 1."""
    dist = [INF] * n
    dist[source] = 0
    pending = deque([source])

    while pending:
        u = pending.popleft()
        for v, weight in adj[u]:
            if weight not in (0, 1):
                raise ValueError("0-1 BFS requires weights 0 or 1")

            candidate = dist[u] + weight
            if candidate < dist[v]:
                dist[v] = candidate
                if weight == 0:
                    pending.appendleft(v)
                else:
                    pending.append(v)

    return dist

def bidirectional_bfs(adj, reverse_adj, source, target):
    """Return one shortest path; pass adj twice for an undirected graph."""
    if source == target:
        return [source]

    n = len(adj)
    parent_from_start = [UNSEEN] * n
    parent_to_target = [UNSEEN] * n
    parent_from_start[source] = -1
    parent_to_target[target] = -1
    forward = [source]
    backward = [target]

    def expand_layer(frontier, graph, own_parent, other_parent):
        next_frontier = []
        meeting = -1
        for u in frontier:
            for v in graph[u]:
                if own_parent[v] != UNSEEN:
                    continue
                own_parent[v] = u
                next_frontier.append(v)
                if meeting == -1 and other_parent[v] != UNSEEN:
                    meeting = v
        return next_frontier, meeting

    def build_path(meeting):
        left = []
        u = meeting
        while u != -1:
            left.append(u)
            u = parent_from_start[u]
        left.reverse()

        right = []
        u = parent_to_target[meeting]
        while u != -1:
            right.append(u)
            u = parent_to_target[u]
        return left + right

    while forward and backward:
        forward, meeting = expand_layer(
            forward, adj, parent_from_start, parent_to_target
        )
        if meeting != -1:
            return build_path(meeting)

        backward, meeting = expand_layer(
            backward, reverse_adj, parent_to_target, parent_from_start
        )
        if meeting != -1:
            return build_path(meeting)

    return []

# Undirected example
n = 5
weighted = [[] for _ in range(n)]
unweighted = [[] for _ in range(n)]
edges = [(0, 1, 1), (0, 2, 0), (2, 3, 0),
         (2, 1, 0), (1, 4, 1), (3, 4, 1)]
for u, v, w in edges:
    weighted[u].append((v, w))
    weighted[v].append((u, w))
    unweighted[u].append(v)
    unweighted[v].append(u)

print("0-1 distances:", zero_one_bfs(n, weighted, 0))
print("Two-way BFS path:", bidirectional_bfs(unweighted, unweighted, 0, 4))

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <stdexcept>
#include <tuple>
#include <utility>

using namespace std;

const int INF = 1e9;
const int UNSEEN = -2;

vector<int> zeroOneBFS(int n, const vector<vector<pair<int, int>>>& adj, int src) {
    vector<int> dist(n, INF);
    dist[src] = 0;
    deque<int> pending{src};

    while (!pending.empty()) {
        int u = pending.front();
        pending.pop_front();

        for (auto [v, weight] : adj[u]) {
            if (weight != 0 && weight != 1) {
                throw invalid_argument("0-1 BFS requires weights 0 or 1");
            }

            int candidate = dist[u] + weight;
            if (candidate < dist[v]) {
                dist[v] = candidate;
                if (weight == 0) {
                    pending.push_front(v);
                } else {
                    pending.push_back(v);
                }
            }
        }
    }
    return dist;
}

vector<int> bidirectionalBFS(
    const vector<vector<int>>& adj,
    const vector<vector<int>>& reverseAdj,
    int source,
    int target
) {
    if (source == target) return {source};

    int n = adj.size();
    vector<int> parentFromStart(n, UNSEEN);
    vector<int> parentToTarget(n, UNSEEN);
    parentFromStart[source] = -1;
    parentToTarget[target] = -1;
    vector<int> forward{source}, backward{target};

    auto expandLayer = [](
        const vector<int>& frontier,
        const vector<vector<int>>& graph,
        vector<int>& ownParent,
        const vector<int>& otherParent
    ) {
        vector<int> next;
        int meeting = -1;
        for (int u : frontier) {
            for (int v : graph[u]) {
                if (ownParent[v] != UNSEEN) continue;
                ownParent[v] = u;
                next.push_back(v);
                if (meeting == -1 && otherParent[v] != UNSEEN) meeting = v;
            }
        }
        return pair<vector<int>, int>{next, meeting};
    };

    auto buildPath = [&](int meeting) {
        vector<int> left, right;
        for (int u = meeting; u != -1; u = parentFromStart[u]) left.push_back(u);
        reverse(left.begin(), left.end());
        for (int u = parentToTarget[meeting]; u != -1; u = parentToTarget[u]) {
            right.push_back(u);
        }
        left.insert(left.end(), right.begin(), right.end());
        return left;
    };

    while (!forward.empty() && !backward.empty()) {
        auto [nextForward, meetForward] = expandLayer(
            forward, adj, parentFromStart, parentToTarget
        );
        forward = move(nextForward);
        if (meetForward != -1) return buildPath(meetForward);

        auto [nextBackward, meetBackward] = expandLayer(
            backward, reverseAdj, parentToTarget, parentFromStart
        );
        backward = move(nextBackward);
        if (meetBackward != -1) return buildPath(meetBackward);
    }
    return {};
}

int main() {
    int n = 5;
    vector<vector<pair<int, int>>> weighted(n);
    vector<vector<int>> unweighted(n);
    vector<tuple<int, int, int>> edges = {
        {0, 1, 1}, {0, 2, 0}, {2, 3, 0}, {2, 1, 0}, {1, 4, 1}, {3, 4, 1}
    };
    for (auto e : edges) {
        int u, v, w;
        tie(u, v, w) = e;
        weighted[u].push_back({v, w});
        weighted[v].push_back({u, w});
        unweighted[u].push_back(v);
        unweighted[v].push_back(u);
    }

    vector<int> dists = zeroOneBFS(n, weighted, 0);
    cout << "0-1 distances: ";
    for (int d : dists) cout << d << " ";
    cout << "\nTwo-way BFS path: ";
    for (int v : bidirectionalBFS(unweighted, unweighted, 0, 4)) cout << v << " ";
    cout << '\n';
    return 0;
}

import java.util.*;

public class SpecializedBFS {
    static final int INF = 1_000_000_000;
    static final int UNSEEN = -2;

    static class Edge {
        int v, w;
        Edge(int v, int w) { this.v = v; this.w = w; }
    }

    public static int[] solve(int n, List<List<Edge>> adj, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;

        ArrayDeque<Integer> dq = new ArrayDeque<>();
        dq.add(src);

        while (!dq.isEmpty()) {
            int u = dq.pollFirst();

            for (Edge e : adj.get(u)) {
                if (e.w != 0 && e.w != 1) {
                    throw new IllegalArgumentException("0-1 BFS requires weights 0 or 1");
                }

                int candidate = dist[u] + e.w;
                if (candidate < dist[e.v]) {
                    dist[e.v] = candidate;
                    if (e.w == 0) {
                        dq.addFirst(e.v);
                    } else {
                        dq.addLast(e.v);
                    }
                }
            }
        }
        return dist;
    }

    static int expandLayer(
        List<Integer> frontier,
        List<List<Integer>> graph,
        int[] ownParent,
        int[] otherParent,
        List<Integer> next
    ) {
        int meeting = -1;
        for (int u : frontier) {
            for (int v : graph.get(u)) {
                if (ownParent[v] != UNSEEN) continue;
                ownParent[v] = u;
                next.add(v);
                if (meeting == -1 && otherParent[v] != UNSEEN) meeting = v;
            }
        }
        return meeting;
    }

    static List<Integer> buildPath(int meeting, int[] fromStart, int[] toTarget) {
        List<Integer> left = new ArrayList<>();
        for (int u = meeting; u != -1; u = fromStart[u]) left.add(u);
        Collections.reverse(left);
        for (int u = toTarget[meeting]; u != -1; u = toTarget[u]) left.add(u);
        return left;
    }

    static List<Integer> bidirectionalBFS(
        List<List<Integer>> adj,
        List<List<Integer>> reverseAdj,
        int source,
        int target
    ) {
        if (source == target) return new ArrayList<>(List.of(source));

        int n = adj.size();
        int[] parentFromStart = new int[n];
        int[] parentToTarget = new int[n];
        Arrays.fill(parentFromStart, UNSEEN);
        Arrays.fill(parentToTarget, UNSEEN);
        parentFromStart[source] = -1;
        parentToTarget[target] = -1;

        List<Integer> forward = new ArrayList<>(List.of(source));
        List<Integer> backward = new ArrayList<>(List.of(target));

        while (!forward.isEmpty() && !backward.isEmpty()) {
            List<Integer> nextForward = new ArrayList<>();
            int meeting = expandLayer(
                forward, adj, parentFromStart, parentToTarget, nextForward
            );
            forward = nextForward;
            if (meeting != -1) return buildPath(meeting, parentFromStart, parentToTarget);

            List<Integer> nextBackward = new ArrayList<>();
            meeting = expandLayer(
                backward, reverseAdj, parentToTarget, parentFromStart, nextBackward
            );
            backward = nextBackward;
            if (meeting != -1) return buildPath(meeting, parentFromStart, parentToTarget);
        }
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Edge>> weighted = new ArrayList<>();
        List<List<Integer>> unweighted = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            weighted.add(new ArrayList<>());
            unweighted.add(new ArrayList<>());
        }

        int[][] edges = {{0,1,1}, {0,2,0}, {2,3,0}, {2,1,0}, {1,4,1}, {3,4,1}};
        for (int[] e : edges) {
            weighted.get(e[0]).add(new Edge(e[1], e[2]));
            weighted.get(e[1]).add(new Edge(e[0], e[2]));
            unweighted.get(e[0]).add(e[1]);
            unweighted.get(e[1]).add(e[0]);
        }

        System.out.println("0-1 distances: " + Arrays.toString(solve(n, weighted, 0)));
        System.out.println("Two-way BFS path: " + bidirectionalBFS(
            unweighted, unweighted, 0, 4
        ));
    }
}

Real-World Applications

Free and paid moves

In a grid, continuing in the current direction might cost 0 while changing direction costs 1. Teleports, preferred roads, and “minimum walls broken” problems have the same binary-cost structure.

Use: 0-1 BFS from the starting state.

Degrees of separation

When looking for one connection chain between two known profiles, two frontiers can meet long before a one-way social-graph crawl reaches the destination.

Use: bidirectional BFS on an unweighted relationship graph.

Implicit state spaces

Word ladders, lock combinations, and small puzzles often generate neighbors on demand. Searching from both known configurations can sharply reduce generated states.

Use: bidirectional BFS when reverse moves are available.

Routing with preferences

A transition can encode “preferred” as cost 0 and “penalized” as cost 1, letting the objective minimize the number of undesirable transitions rather than physical length.

Use: 0-1 BFS only when the model truly has two additive costs.

Exercises

Check the invariants

For the directed edges $s\to a$ (1), $s\to b$ (0), $b\to a$ (0), and $a\to t$ (1), write the deque after every successful relaxation.
Construct the smallest example where marking a 0-1 BFS vertex permanently visited when first enqueued gives the wrong distance.
Prove by induction that the deque contains only two consecutive distance values and that all smaller labels appear first.

Hint for 2: let one vertex be reachable directly by cost 1 and indirectly through two zero-cost edges.

Reason about two-way search

Run alternating-layer bidirectional BFS on a path of length 7. At which layer does the first intersection appear?
For a directed graph, give an example where using the original adjacency list from the target incorrectly reports “no path.” Then fix it with the transpose.
Challenge: modify the implementation to expand the smaller frontier while retaining distances and a provably safe stopping condition.

A safe weighted-style rule tracks the best complete path seen and stops only when the minimum possible unfinished path cannot beat it.

Limitations

Pitfall	Why it fails	Better choice or repair
A 0-1 edge has weight 2 or -1	The two-level deque invariant disappears.	Use Dijkstra for non-negative weights or Bellman-Ford when negative edges are possible.
Scaling $\{0,W\}$ without explanation	The code expects 0 and 1, not arbitrary $W$.	If $W>0$ is the only positive weight, divide all weights by $W$, run 0-1 BFS, then multiply finite distances by $W$.
No known target	There is nowhere to seed the reverse search.	Use ordinary BFS or 0-1 BFS for all-destination distances.
Backward search follows forward directed edges	It explores vertices reachable from $t$, not vertices that can reach $t$.	Build and search the transpose graph.
Stop when any two discovered sets touch	With unbalanced or weighted expansion, the first touch need not certify the best total distance.	Expand complete balanced BFS layers, or maintain a best path plus a lower-bound termination test.

Optimization is conditional, not automatic

Bidirectional BFS can use more memory than expected because it stores two visited sets, and it may offer little benefit on narrow paths, highly asymmetric graphs, or when reverse neighbors are expensive to generate. 0-1 BFS is excellent inside its exact weight contract and invalid outside it.

Cookie Consent

0-1 BFS & Bidirectional Search

Contents

Origins and the Shared Idea

One principle, two different shortcuts

Choose the Right Search

Costs are 0 or 1

One source, one target

0-1 BFS: A Two-Level Priority Queue

The invariant that replaces a heap

Bidirectional BFS: Meet Near the Middle

Directed graphs need reverse edges

Worked Examples and Failure Intuition

0-1 BFS trace: why a permanent visited flag is dangerous

Do not copy ordinary BFS's visited-on-enqueue rule

Bidirectional trace: six edges become two depth-3 searches

Path Reconstruction

0-1 BFS predecessor

Two parent forests

Complexity Without the Hand-Waving

Implementations

Real-World Applications

Free and paid moves

Degrees of separation

Implicit state spaces

Routing with preferences

Exercises

Check the invariants

Reason about two-way search

Limitations

Optimization is conditional, not automatic

Cookie Consent

0-1 BFS & Bidirectional Search

Contents

Origins and the Shared Idea

One principle, two different shortcuts

Choose the Right Search

Costs are 0 or 1

One source, one target

0-1 BFS: A Two-Level Priority Queue

The invariant that replaces a heap

Bidirectional BFS: Meet Near the Middle

Directed graphs need reverse edges

Worked Examples and Failure Intuition

0-1 BFS trace: why a permanent visited flag is dangerous

Do not copy ordinary BFS's visited-on-enqueue rule

Bidirectional trace: six edges become two depth-3 searches

Path Reconstruction

0-1 BFS predecessor

Two parent forests

Complexity Without the Hand-Waving

Implementations

Real-World Applications

Free and paid moves

Degrees of separation

Implicit state spaces

Routing with preferences

Exercises

Check the invariants

Reason about two-way search

Limitations

Optimization is conditional, not automatic

Related Deep Dives

Graph Theory Series

Dial's Algorithm

A* Search & Heuristics