[python刷题模板] 0-1BFS

一、 算法&数据结构

1. 描述

0-1BFS目前我只在最短路问题遇到，使用双端队列优化为复杂度O(VE)。
当边权只有0或1时，可以使用0-1BFS，否则请使用dijkstra等最短路算法。
实际上0-1BFS和dijkstra是很相似的，都是控制下个节点的访问顺序；不同之处在于，dijkstra需要给堆传入优先级来决定优先访问哪个；0-1BFS的优先级是明确的。
由于复杂度提升的不多，赛中还是建议优先使用dijkstra吧。
1
2
3
4

• 当边权只有1时，我们可以用朴素BFS来找最短路；当边权有非负数时，我们可以用dijkstra。
• 它们的特点是用队列/优先队列来保证：优先出队的一定是当前最该处理的节点。
• 考虑当边权只有0或者1的情况，假设当前从u转移到v：
  • 若w=1，则v的最短路d=dist[u]+1，应入队；推之前队列中不存在dist小于d的节点。显然v应该最后出队，则dq.append(v)。
  • 若w=0，则v的最短路d=dist[u]+0=dist[u]，应入队；我们知道u是当前最小节点，如果v的优先级=u，那么完全可以立刻处理，即优先出队（下一个出队），则dq.appendleft(v)。

2. 复杂度分析

1. O(VE)，即节点数乘边数。

3. 常见应用

1. 边权只有0或1的最短路搜索。

4. 常用优化

1. dis初始化为inf，避免使用vis标记数组。

二、 模板代码

1. 去除障碍物的矩阵搜索

例题: 2290. 到达角落需要移除障碍物的最小数目

• 目标位置存在则边权是1.否则是0

DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m,n = len(grid),len(grid[0])
        def inside(x,y):
            return 0<=x<m and 0<=y<n
        dist = [[inf]*n for _ in range(m)]
        dist[0][0] = 0
        q = deque([(0,0)])
        while q:
            x,y = q.popleft()
            if x == m-1 and y == n - 1:
                return dist[x][y]
            for dx,dy in DIRS:
                a,b = x+dx,y+dy 
                
                if inside(a,b) :
                    d = dist[x][y]+grid[a][b]
                    if dist[a][b]>d:
                        dist[a][b] = d
                        if grid[a][b] == 0:
                            q.appendleft((a,b))
                        else:
                            q.append((a,b))                
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. 修改传送方向的矩阵搜索

链接: 1368. 使网格图至少有一条有效路径的最小代价

• 显然如果顺着原方向，代价（修改次数）=0；否则代价=1.
• 代码实现时，对dir按题意顺序，然后偏移下标来模拟方向。

DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m,n = len(grid),len(grid[0])
        def inside(x,y):
            return 0<=x<m and 0<=y<n
        dist = [[inf]*n for _ in range(m)]
        dist[0][0] = 0
        q = deque([(0,0,0)])
        while q:
            c,x,y = q.popleft()
            if x == m-1 and y == n-1:
                return c
            if c > dist[x][y]:continue
            for i,(dx,dy) in enumerate(DIRS,1):
                a,b = x+dx,y+dy 
                if inside(a,b):
                    w = int(grid[x][y] != i)
                    d = c + w
                    if d < dist[a][b]:
                        dist[a][b] = d 
                        if w>0:
                            q.append((d,a,b))
                        else:
                            q.appendleft((d,a,b))
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

三、其他

1. 其实用不太到这个算法，考试时候肯定是优先用dijkstra了

四、更多例题

五、参考链接

• 链接: [python刷题模板] 最短路(Dijkstra)