0-1 BFS

What · 是什么

0-1 BFS 是处理『边权只有 0 或 1』（可推广为 0 或任意常数 k）图的最短路算法，O(V+E) 时间 O(V) 空间，比 Dijkstra 少一个 log。用双端队列（deque）维护：0 权边扩展的节点插入队首，1 权边扩展的节点插入队尾，从而保证队内距离单调不降（类 BFS 的分层性质），每个节点至多入队少数几次。是边权二进制图中最高效的算法，也常作为分层图、图论建模优化。

Why · 为什么

How · 实现

伪代码

from collections import deque
def bfs01(adj, s):
  dis=[INF]*n; dis[s]=0; dq=deque([s])
  while dq:
    u=dq.popleft()
    for v, w in adj[u]:       # w in {0,1}
      if dis[u]+w < dis[v]:
        dis[v]=dis[u]+w
        if w==0: dq.appendleft(v)
        else: dq.append(v)
  return dis

Python 实现

from collections import deque


def bfs01(n, adj, s):
    """0-1 BFS: 边权仅 0/1 的单源最短路, O(V+E).
    adj: 邻接表 adj[u]=[(v,w),...], w in {0,1}."""
    INF = float('inf')
    dis = [INF] * n
    dis[s] = 0
    dq = deque([s])
    while dq:
        u = dq.popleft()
        du = dis[u]
        for v, w in adj[u]:
            nd = du + w
            if nd < dis[v]:
                dis[v] = nd
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dis


def bfs01_path(n, adj, s, t):
    """带路径重建: 返回 (dist, path)"""
    INF = float('inf')
    dis = [INF] * n
    pre = [-1] * n
    dis[s] = 0
    dq = deque([s])
    while dq:
        u = dq.popleft()
        du = dis[u]
        for v, w in adj[u]:
            nd = du + w
            if nd < dis[v]:
                dis[v] = nd
                pre[v] = u
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    if dis[t] == INF:
        return INF, []
    path = []
    cur = t
    while cur != -1:
        path.append(cur)
        cur = pre[cur]
    path.reverse()
    return dis[t], path


if __name__ == "__main__":
    # 图: 0-1(1),0-2(0),1-3(0),2-3(1),2-4(1),3-4(0)
    adj = [[] for _ in range(5)]
    for u, v, w in [(0, 1, 1), (0, 2, 0), (1, 3, 0), (2, 3, 1), (2, 4, 1), (3, 4, 0)]:
        adj[u].append((v, w))
    dis = bfs01(5, adj, 0)
    assert dis == [0, 1, 0, 1, 1], dis
    d, p = bfs01_path(5, adj, 0, 4)
    assert d == 1 and p == [0, 2, 4], (d, p)  # 0->2(0)->4(1)=1 为最短路

    # 与 Dijkstra 交叉验证
    import heapq, random
    random.seed(53)

    def dijkstra(n, adj, s):
        INF = float('inf')
        dis = [INF] * n
        dis[s] = 0
        pq = [(0, s)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dis[u]:
                continue
            for v, w in adj[u]:
                nd = d + w
                if nd < dis[v]:
                    dis[v] = nd
                    heapq.heappush(pq, (nd, v))
        return dis

    for _ in range(300):
        n = random.randint(1, 8)
        a = [[] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if i != j and random.random() < 0.3:
                    a[i].append((j, random.randint(0, 1)))
        s = random.randrange(n)
        d1 = bfs01(n, a, s)
        d2 = dijkstra(n, a, s)
        for i in range(n):
            assert d1[i] == d2[i], (i, d1[i], d2[i])
    print("All tests passed.")

易错点

• 用普通队列代替 deque 会破坏单调性，结果错误
• 0 权边插队首、1 权边插队尾，顺序写反会 TLE/错误
• dis 初始 INF 且更新后必须判断 nd<dis[v] 才能入队，否则死循环（0 权环）
• 边权不止 0/1 时硬套 0-1 BFS 会错，须换 Dijkstra
• 0 权环可能让节点多次入队，dis 检查可避免无限循环

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/bfs/
• CP-Algorithms✓ https://cp-algorithms.com/graph/01_bfs.html
• 书籍✓ CPH ch13 pp133-142