0-1 BFS

有序前沿与路径 · HTML

数学 / 逻辑形态

relax u→v,w∈{0,1}；改善后 w=0 用 appendleft，w=1 用 append，使 deque 中待处理标签保持至多相差一层。

识别信号

• 动作分成免费与花费一次两类。
• 边权严格属于 {0,1}。
• 目标最小化付费动作数量而非总动作数。
• Dijkstra 可做但二叉堆显得过重。

容易误判的相似信号

核心不变量

deque 中从左到右的候选距离非递减；0 边不改变层级，1 边进入下一层。

状态、转移与处理顺序

Python 骨架

from collections import deque

def zero_one_bfs(graph, start):
    inf = float('inf')
    dist = {u: inf for u in graph}
    dist[start] = 0
    dq = deque([start])
    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            if w not in (0, 1):
                raise ValueError('weight must be 0 or 1')
            nd = dist[u] + w
            if nd < dist.get(v, inf):
                dist[v] = nd
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

正确性思路

1. 从左端弹出的候选具有最小待处理距离：免费边留在当前距离，付费边只进入下一距离。
2. 每次 relaxation 都产生一条真实路径上界，且更优标签被放到正确优先级。
3. 这等价于对 0/1 权 Dijkstra 的堆顺序做两桶压缩，因此最终 dist 最优。

复杂度

边界条件

• 全零边时所有同分量距离为 0。
• 全一边时退化为普通 BFS。
• 零权环不能依靠 visited 过早封死改善。
• 邻接表中的非法权值应断言或改用 Dijkstra。

错误模式

选择与排除规则

• 权值集合恰为 {0,1}：优先 0-1 BFS。
• 只有 {0,c} 且 c 固定正数：缩放后同样适用。
• 权值出现第三种非等价值：回到 Dijkstra。

相关模板

原创微型例子

Recall prompts

• 为什么 0 边放左端、1 边放右端？
• 为何不能简单 first-seen visited？
• 0-1 BFS 与两桶 Dijkstra 有何等价关系？

我的补充