BFS 的核心思想应该不难理解的,就是把一些问题抽象成图,从一个点开始,向四周开始扩散。一般来说,我们写 BFS 算法都是用「队列」这种数据结构,每次将一个节点周围的所有节点加入队列。
BFS 相对 DFS 的最主要的区别是:BFS 找到的路径一定是最短的,但代价就是空间复杂度比 DFS 大很多,至于为什么,我们后面介绍了框架就很容易看出来了。
要说框架的话,我们先举例一下 BFS 出现的常见场景好吧,问题的本质就是让你在一幅「图」中找到从起点 **start**
到终点 **target**
的最近距离,这个例子听起来很枯燥,但是 BFS 算法问题其实都是在干这个事儿,把枯燥的本质搞清楚了,再去欣赏各种问题的包装才能胸有成竹嘛。
这个广义的描述可以有各种变体,比如走迷宫,有的格子是围墙不能走,从起点到终点的最短距离是多少?如果这个迷宫带「传送门」可以瞬间传送呢?
再比如说两个单词,要求你通过某些替换,把其中一个变成另一个,每次只能替换一个字符,最少要替换几次?
# 模版
def bfs(self, nums):
queue = [起始点] # 队列实现BFS
visited = set() # 记录访问过的元素点,避免“回头”访问,陷入循环
visited.add(起始点) # 将起点加入队列
depth = 0 # 记录扩散的步数
while queue:
# 将所有节点同时向前扩散一步
for _ in range(len(queue)):
cur = queue.pop(0)
if 找到目标:
return depth
# 将cur的【所有相邻且没被访问过的节点】加入队列
for near in cur的邻近节点:
if near not in visited:
queue.append(near)
visited.add(near)
depth += 1 # 记录路径长度
# 二叉树的最小深度
class Solution:
'''BFS迭代方法'''
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
depth = 1
queue = [root]
while queue:
for i in range(len(queue)):
node = queue.pop(0) # 切记要先取出
if not node.left and not node.right:
return depth
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1
return depth
岛屿数量
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
输入:grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出:1
输入:grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出:3
class Solution(object):
def numIslands(self, grid):
# 方法一:广度优先遍历 BFS
def bfs(grid, i, j):
queue = [[i, j]]
while queue:
[i, j] = queue.pop(0)
if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
grid[i][j] = '0'
queue += [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '0':
continue
bfs(grid, i, j)
count += 1
return count
# 方法二:深度优先遍历DFS,这种好理解
def dfs(grid, i, j):
if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0':
return
# 将岛屿所有节点删除,以免之后重复搜索相同岛屿
grid[i][j] = '0'
dfs(grid, i + 1, j)
dfs(grid, i, j + 1)
dfs(grid, i - 1, j)
dfs(grid, i, j - 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
# 从 (i, j) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索
dfs(grid, i, j)
count += 1
return count
打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ,一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。
字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。
输入:deadends = [“0201”,”0101”,”0102”,”1212”,”2002”], target = “0202”
输出:6
解释:
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的,
因为当拨动到 “0102” 时这个锁就会被锁定。
输入: deadends = [“8888”], target = “0009”
输出:1
解释:
把最后一位反向旋转一次即可 “0000” -> “0009”。
class Solution(object):
def openLock(self, deadends, target):
# 可抽象成最短路径问题,由起始点'0000'到目标target的最短路径长度,路径中不能经过死亡数字。套用上面框架即可。
# BFS
queue = ['0000']
visited = set()
visited.add('0000')
deadset = set(deadends)
depth = 0
while queue:
for _ in range(len(queue)):
cur = queue.pop(0)
if cur in deadset:
continue # 如果cur是死亡数字,则不选这条路径
if cur == target:
return depth # 如果cur = target,则找到目标,返回depth
# 将当前cur元素的所有邻近元素加入队列和visited
for i in range(4):
up = self.up(cur, i)
if up not in visited:
queue.append(up)
visited.add(up)
down = self.down(cur, i)
if down not in visited:
queue.append(down)
visited.add(down)
depth += 1
return -1
def up(self, s, i):
"""将字符串s的第i个元素向上拨动一位,并返回拨动后的字符串"""
s_list = list(s)
if s_list[i] == '9':
s_list[i] = '0'
else:
s_list[i] = str(int(s_list[i])+1)
return "".join(s_list)
def down(self, s, i):
"""将字符串s的第i个元素向下拨动一位,并返回拨动后的字符串"""
s_list = list(s)
if s_list[i] == '0':
s_list[i] = '9'
else:
s_list[i] = str(int(s_list[i])-1)
return "".join(s_list)
迷宫
mete = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
class Solution(object):
# 方法一:深度优先,但是不是最优解
def dfs_stack(self, start, end, mete):
stack = [start]
while stack:
now = stack[-1]
if now == end:
print(stack)
return True
x, y = now
mete[x][y] = 2
if mete[x - 1][y] == 0:
stack.append([x - 1, y])
continue
elif mete[x][y - 1] == 0:
stack.append([x, y - 1])
continue
elif mete[x + 1][y] == 0:
stack.append([x + 1, y])
continue
elif mete[x][y + 1] == 0:
stack.append([x, y + 1])
continue
else:
stack.pop()
return False
# 方法二:广度优先,最优解
def bfs_queue(self, start, end, mete):
def dfs(next_x, next_y):
if mete[next_x][next_y] == 0:
queue.append([next_x, next_y, len(tmp) - 1]) # 如果不统计路径,这个len(tmp) - 1就没用
mete[next_x][next_y] = 2
x1, y1 = start
queue = [[x1, y1, -1]] # 如果不统计路径,这个1就没用
mete[x1][y1] = 2
tmp = []
while queue:
now = queue.pop(0)
tmp.append(now)
if now[0:2] == end:
# 这段代码统计路径路径
# path = []
# i = len(tmp) - 1
# while i >= 0:
# path.append(tmp[i][0:2])
# i = tmp[i][2]
# path = path[::-1]
# print(path)
return True
dfs(now[0] - 1, now[1])
dfs(now[0], now[1] + 1)
dfs(now[0] + 1, now[1])
dfs(now[0], now[1] - 1)
else:
return False
start = [1, 1]
end = [6, 8]
A = Solution()
print(A.bfs_queue(start, end, mete))
print(A.dfs_stack(start, end, mete))