遍历：BFS

BFS每次搜索的时候从所有的frontier开始扩展，并保留新的起点在frontier。BFS可以用从一点（或者多源）开始寻找最近的答案，或者无权有向图或者无向两点之间的最短距离。

DFS与BFS的比较：

  • 在有一些问题中，BFS会比DFS更加高效。例如在社交网络想要寻找两个朋友的链接度，DFS可能会钻进死胡同去搜索另一个朋友所有的subtree再回头过来找与他们更亲近的朋友。

  • 在分布式算法中，BFS作为“多兵作战“的算法比DFS的“单打独斗“更合适。比如说在crawl网页的过程中，我们可以暂时把目前爬到的域名frontier存在硬盘或者缓存中，然后让多个线程从frontier中选取一个域名继续爬。

回看前面DFS里的迷宫题，我们用BFS可以这样求解。

queue = [enter]
paths = {enter: [enter]}
while queue:
    v = queue.pop(0)
    if v==exit: return path[v]
    for u in neighbors(p):
        if u in path: continue
        if wall(u, v): continue
        queue.append(u)
        paths[u] = paths[v] + [u]
return []

这里我们简单起见只返回了任一可行解。留意这里因为要记录最后可行解的路径，我们用paths: point -> path来保存在任一点到达这一点的路径，并代替了使用vis数组来判断是否已经访问了某一点。

例题：打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        nums = "0123456789"
        def neighbor(s):
            for i in range(4):
                yield s[:i]+nums[(nums.index(s[i])+1)%10]+s[i+1:]
                yield s[:i]+nums[(nums.index(s[i])-1)%10]+s[i+1:]
        start = "0000"
        if start in deadends: return -1
        queue = [(start, 0)]
        vis = set([start] + deadends)
        while queue:
            s, step = queue.pop(0)
            if s==target: return step
            for ns in [x for x in neighbor(s) if x not in vis]:
                queue.append((ns, step+1))
                vis.add(ns)
        return -1

节省空间的双源BFS

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        nums = "0123456789"
        def neighbor(s):
            for i in range(4):
                yield s[:i]+nums[(nums.index(s[i])+1)%10]+s[i+1:]
                yield s[:i]+nums[(nums.index(s[i])-1)%10]+s[i+1:]
        
        start = "0000"
        if start==target: return 0
        if start in deadends: return -1
        vis = set([start, target]+deadends)
        vis1, vis2 = set([start]), set([target])
        step = 0
        while vis1 and vis2:
            if len(vis1)>len(vis2): vis1, vis2 = vis2, vis1
            vislevel = set()
            for s in vis1:
                for ns in neighbor(s):
                    if ns in vis2: return step+1
                    if ns not in vis|vislevel:
                        vislevel.add(ns)
                        vis.add(ns)
            step += 1
            vis1 = vislevel
        return -1

例题：离建筑物最近的距离

输入：[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0
输出：7 
解析：
给定三个建筑物 (0,0)、(0,4) 和 (2,2) 以及一个位于 (0,2) 的障碍物。
由于总距离之和 3+3+1=7 最优，所以位置 (1,2) 是符合要求的最优地点，故返回7。
def shortestDistance(grid):
    m, n = len(grid), len(grid[0])
    dx, dy = (1, -1, 0, 0), (0, 0, 1, -1)
    def inboard(x, y, vis):
        return 0<=x<m and 0<=y<n and grid[x][y]==0 and not vis[x][y]

    def expand(i, j):
        queue.append((i, j, 0))
        vis = [[False]*n for _ in range(m)]
        while queue:
            x, y, d = queue.pop(0)
            for di in range(4):
                nx, ny = x+dx[di], y+dy[di]
                if not inboard(nx, ny, vis): continue
                cnts[nx][ny] += 1
                dist[nx][ny] += d+1
                vis[nx][ny] = True
                queue.append((nx, ny, d+1))
    
    cnts = [[0]*n for _ in range(m)]
    dist = [[0]*n for _ in range(m)]
    queue = []
    cnt = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j]==1:
                cnt += 1
                expand(i, j)
    
    res = float('inf')
    for i in range(m):
        for j in range(n):
            if cnts[i][j]==cnt:
                res = min(res, dist[i][j])
    return res if res < float('inf') else -1

例题：撞球迷宫

和一般的迷宫不一样，如果我们在Tilt Maze里面从起点找终点，我们就加入状态来表示球的行进方向，而且要多一个状态来表示“静止”。下面BFS和DFS中，用0-3来表示四个方向，用4来表示静止状态。

Tilt Mazes
def solveTiltMazeBFS(maze, start, goal):
    m, n = len(maze), len(maze[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    def validCell(x, y, i):
        return 0<=x<m and 0<=y<n and (x, y, i) not in path and maze[x][y] != 'x'

    sx, sy = start
    queue = [(sx, sy, 4)]
    path = {(sx, sy, 4): [(sx, sy, 4)]}
    while queue:
        x, y, d = queue.pop(0)
        if (x, y) == goal:
            return path[(x, y, d)]
        curPath = path[(x, y, d)]
        if d==4: # stationary ball
            for i in range(4):
                dx, dy = directions[i]
                nx, ny = x+dx, y+dy
                if validCell(nx, ny, i):
                    queue.append((nx, ny, i))
                    path[(nx, ny, i)] = curPath + [(nx, ny, i)]
        else: # if ball is rolling
            dx, dy = directions[d]
            nx, ny = x+dx, y+dy
            if validCell(nx, ny, d):
                queue.append((nx, ny, d))
                path[(nx, ny, d)] = curPath + [(nx, ny, d)]
            if not validCell(nx, ny, 4):
                queue.append((x, y, 4))
                path[(x, y, 4)] = curPath + [(x, y, 4)]
    return []

# tiltMaze = [
# 'Sx--',
# '----',
# 'xx--',
# '--G-',
# '----',
# ]
# path = solveTiltMazeBFS(tiltMaze, (0,0), (3,2))

Previous遍历：DFS/回溯Next动态规划

Last updated

Was this helpful?