BFS variants

Standard BFS explores a single starting node, one distance layer at a time. Four variations adapt that same idea to more specific problem structures. You can start from several nodes at once, handle edge weights of 0 and 1 without a heap, follow forced zero-cost moves safely, or search backward from a target instead of forward from a source.

Multi-source BFS

When several nodes are equally good starting points, initialize the queue with all of them at distance 0. BFS then explores outward from all sources in parallel. This is useful when you need the closest source to every other node, or the shortest distance from any source.

1from collections import deque2
3
4def multisource_bfs(adj, sources):5    """BFS from multiple sources at once."""6    n = len(adj)7    dist = [-1] * n8    queue = deque()9
10    for src in sources:11        dist[src] = 012        queue.append(src)13
14    while queue:15        u = queue.popleft()16        for v in adj[u]:17            if dist[v] == -1:18                dist[v] = dist[u] + 119                queue.append(v)20
21    return dist22
23
24adj = [25    [1, 2],26    [0, 3],27    [0, 4],28    [1, 5],29    [2, 5],30    [3, 4]31]32
33distances = multisource_bfs(adj, [0, 3])34print("Distances from sources [0, 3]:", distances)

Distances from sources [0, 3]: [0, 1, 1, 0, 2, 1]

Multi-source BFS assigns each node its distance to the nearest source. The algorithm is identical to single-source BFS except you push multiple nodes into the initial queue.

0-1 BFS with deque

When edges have weight 0 or 1 only, you do not need a full priority queue (heap). Instead, use a deque (double-ended queue).

For each edge:

• If the edge weight is 0, push the neighbor to the front (appendleft).
• If the edge weight is 1, push the neighbor to the back (append).

This ensures nodes are processed in non-decreasing order of distance without sorting.

1from collections import deque2
3
4def zero_one_bfs(adj, start):5    """0-1 BFS using deque with appendleft for weight-0 edges."""6    n = len(adj)7    dist = [float('inf')] * n8    dist[start] = 09    queue = deque([start])10
11    while queue:12        u = queue.popleft()13        for v, w in adj[u]:14            if dist[u] + w < dist[v]:15                dist[v] = dist[u] + w16                if w == 0:17                    queue.appendleft(v)18                else:19                    queue.append(v)20
21    return dist22
23
24adj = [25    [(1, 0), (2, 1)],26    [(0, 0), (3, 1)],27    [(0, 1), (4, 0)],28    [(1, 1), (5, 1)],29    [(2, 0), (5, 1)],30    [(3, 1), (4, 1)]31]32
33distances = zero_one_bfs(adj, 0)34print("0-1 BFS distances from node 0:", distances)

0-1 BFS distances from node 0: [0, 0, 1, 1, 1, 2]

0-1 BFS is much faster than a heap-based Dijkstra when edge weights are restricted to 0 and 1. It runs in $O(V + E)$ time.

Why does this work? Standard BFS processes nodes in layers by distance. In a weighted graph, Dijkstra uses a heap to process nodes in order of distance, and each node's extraction costs $O(\log E)$. With only weights 0 and 1, you know that all distance-$d$ nodes are reachable before distance-$d+1$ nodes. A weight-0 edge keeps you at the same distance (append to front), and a weight-1 edge moves you to the next distance (append to back). The deque handles this automatically without sorting.

Zero-cost moves and conveyors

Some problems have forced moves (conveyors, teleporters) that consume no time or resources. To handle these, follow all zero-cost moves exhaustively before adding the node to the normal BFS queue. Detect cycles by tracking which nodes are currently being processed.

1from collections import deque2
3
4def conveyor_bfs(adj, conveyors, start):5    """BFS handling forced zero-cost moves (conveyors)."""6    n = len(adj)7    dist = [-1] * n8    visited = [False] * n9
10    def follow_conveyors(u, in_progress):11        """Follow zero-cost moves, detect cycles."""12        if in_progress[u]:13            return u14        in_progress[u] = True15        if u in conveyors:16            u = follow_conveyors(conveyors[u], in_progress)17        in_progress[u] = False18        return u19
20    dist[start] = 021    queue = deque([start])22
23    while queue:24        u = queue.popleft()25        u = follow_conveyors(u, [False] * n)26        if visited[u]:27            continue28        visited[u] = True29
30        for v in adj[u]:31            if not visited[v]:32                dist[v] = dist[u] + 133                queue.append(v)34
35    return dist36
37
38adj = {39    0: [1, 2],40    1: [3],41    2: [4],42    3: [5],43    4: [5],44    5: []45}46conveyors = {1: 2}47
48distances = conveyor_bfs(adj, conveyors, 0)49print("Distances with conveyors:", distances)

Distances with conveyors: [0, 1, 1, -1, 2, 3]

The key is to recognize when a zero-cost move creates a cycle and stop following that chain. Otherwise, you risk infinite loops. Marking nodes as "in progress" prevents revisiting the same cycle.

For example, imagine a conveyor from node 1 to node 2, and another from node 2 back to node 1. If you naively follow zero-cost moves, you loop infinitely: 1 → 2 → 1 → 2 → ... Instead, mark 1 as in-progress, follow to 2, then check if 2 is in-progress. Since it is not yet, move to it and mark it in-progress. When you check the edge from 2 back to 1, you see 1 is already in-progress and stop. Unmark both nodes and continue with normal BFS. This prevents infinite loops while still following valid zero-cost moves.

Reverse-graph BFS

Sometimes it is easier to search from the target backward. Build the reverse graph (flip all edges) and run BFS from the target. Distances in the reverse graph are the distances from each node to the target in the original graph.

1from collections import deque2
3
4def reverse_bfs(adj, target):5    """BFS on reverse graph to compute distances to target."""6    n = len(adj)7    rev_adj = [[] for _ in range(n)]8
9    for u in range(n):10        for v in adj[u]:11            rev_adj[v].append(u)12
13    dist = [-1] * n14    dist[target] = 015    queue = deque([target])16
17    while queue:18        u = queue.popleft()19        for v in rev_adj[u]:20            if dist[v] == -1:21                dist[v] = dist[u] + 122                queue.append(v)23
24    return dist25
26
27adj = [28    [1, 2],29    [3],30    [4],31    [5],32    [5],33    []34]35
36distances = reverse_bfs(adj, 5)37print("Distance from each node to target 5:", distances)

Distance from each node to target 5: [3, 2, 2, 1, 1, 0]

This is useful when the target is given but the starting nodes are many or implicit. For example, find the shortest time to reach an exit from every room in a building.

Reverse-graph BFS suits time-based problems too. Given daily tasks and a final deadline state, reversing the graph lets you compute how much time is left once you reach each state, working backward from the deadline. Building the reverse graph takes $O(V + E)$ time (iterate edges and add reversed copies), and then BFS is $O(V + E)$ as usual.

Why these variants matter

Multi-source BFS fits problems that need the closest source to every node. It also fits problems that hand you several starting points by design. 0-1 BFS skips the heap Dijkstra's algorithm needs, so it runs faster when edge weights are restricted to 0 and 1. Zero-cost moves force you to follow chains and handle the resulting structure carefully. Reverse-graph BFS works well when the target is known but the sources are implicit or numerous.

Contest problems often mix these variants. A problem might start with zero-cost moves, follow them completely, then continue over ordinary weight-1 edges toward a target. Searching backward from that target with the reverse graph is often cleaner than tracking every path forward. Senior 3 and 4 problems combine these techniques regularly.

Common mistakes

• Forgetting to initialize all sources: In multi-source BFS, every source must start at distance 0. If you initialize only one, you get single-source BFS.
• Mixing up appendleft and append: In 0-1 BFS, weight-0 edges go to the front (appendleft), and weight-1 edges go to the back (append). Swapping them breaks the order.
• Infinite loops with conveyors: If you follow zero-cost moves without cycle detection, you can loop forever. Always mark nodes as visited or in-progress.
• Forgetting to reverse all edges: When building the reverse graph, flip every edge. An undirected edge becomes a pair of reversed edges in both directions.
• Confusing distance in the original vs. reverse graph: Distance from A to B in the original graph equals distance from B to A in the reverse graph. If you query the reverse graph, remember to query with swapped endpoints.

Recap

Multi-source BFS starts from several nodes at distance 0. 0-1 BFS avoids a heap by using deque with appendleft for weight-0 edges. Zero-cost moves require cycle detection to avoid infinite loops. Reverse-graph BFS reaches a target by searching backward. These variants extend BFS to handle richer graph structures.