BFS (Breadth-first Search)

BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。

BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度可能比 DFS 大很多。

我们先举例一下 BFS 出现的常见场景好吧，问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离。

这个广义的描述可以有各种变体，比如走迷宫，有的格子是围墙不能走，从起点到终点的最短距离是多少？如果这个迷宫带「传送门」可以瞬间传送呢？

再比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？

再比如说连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？

再比如……

净整些花里胡哨的，本质上看这些问题都没啥区别，就是一幅「图」，让你从一个起点，走到终点，问最短路径。这就是 BFS 的本质。

为什么 BFS 可以找到最短距离，DFS 不行吗？

首先，你看 BFS 的逻辑，depth 每增加一次，队列中的所有节点都向前迈一步，这保证了第一次到达终点的时候，走的步数是最少的。

DFS 不能找最短路径吗？其实也是可以的，但是时间复杂度相对高很多。你想啊，DFS 实际上是靠递归的堆栈记录走过的路径，你要找到最短路径，肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长对不对？而 BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。

形象点说，DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动。这个应该比较容易理解吧。

既然 BFS 那么好，为啥 DFS 还要存在？

BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。

还是拿刚才我们处理二叉树问题的例子，假设给你的这个二叉树是满二叉树，节点数为 N，对于 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，也就是 O(logN)。

但是你想想 BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是 N/2，用 Big O 表示的话也就是 O(N)。

由此观之，BFS 还是有代价的，一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些（主要是递归代码好写）。

双向 BFS 优化

双向 BFS 还是遵循 BFS 算法框架的，只是不再使用队列，而是使用 HashSet 方便快速判断两个集合是否有交集。

另外的一个技巧点就是 while 循环的最后交换 q1 和 q2 的内容，所以只要默认扩散 q1 就相当于轮流扩散 q1 和 q2。

其实双向 BFS 还有一个优化，就是在 while 循环开始时做一个判断：

# ...
while not q1.empty() and not q2.empty():
    if q1.qsize() > q2.qsize():
        # 交换 q1 和 q2
        temp = q1
        q1 = q2
        q2 = temp
    # ...

题目

TODO

解析

111. Minimum Depth of Binary Tree

# BFS
class Solution:
	def minDepth(self, root: Optional[TreeNode]) -> int:
		if not root:
			return 0

		min_depth = float('inf')
		queue = [root]
		level = 0
		while queue:
			for i in range(len(queue)):
				n = queue.pop(0)
				if not n.left and not n.right:
					min_depth = min(min_depth, level + 1)
					break

				if n.left:
					queue.append(n.left)
				if n.right:
					queue.append(n.right)

			if min_depth != float('inf'):
				return min_depth
			level += 1

# DFS
class Solution:
	def minDepth(self, root: Optional[TreeNode]) -> int:
		min_depth = [float('inf')]

		def dfs(root, depth):
			if not root:
				return 0
			if not root.left and not root.right:
				min_depth[0] = min(min_depth[0], depth + 1)
				return

			dfs(root.left, depth + 1)
			dfs(root.right, depth + 1)

		if not root:
			return 0
		dfs(root, 0)
		return min_depth[0]

Graph - 752. Open the Lock

任何一个密码，拨动一次，最多有8种变化
1. 以此类推，对于拨动后的每一个结果，再拨动一次，也有8种结果
拨到 deadends时，需要跳过，因为 deadends不能被拨到
用一个 visit hashset来记录已经访问过的节点

class Solution:
	def openLock(self, deadends: List[str], target: str) -> int:
		if "0000" in deadends:
			return -1

		def children(lock):
			res = []
			for i in range(4):
				digit = str((int(lock[i]) + 1) % 10)
				res.append(lock[:i] + digit + lock[i + 1:])

				digit = str((int(lock[i]) - 1 + 10) % 10)
				res.append(lock[:i] + digit + lock[i + 1:])
			return res

		queue = [("0000", 0)]  # (lock, count)
		visit = set(deadends)
		while queue:
			lock, count = queue.pop(0)
			if lock == target:
				return count
			for child in children(lock):
				if child not in visit:
					visit.add(child)
					queue.append((child, count + 1))
		return -1

ref

https://www.youtube.com/watch?v=Pzg3bCDY87w

[Topic] BFS (Breadth-first Search)

BFS (Breadth-first Search)

双向 BFS 优化

题目

解析

111. Minimum Depth of Binary Tree

Graph - 752. Open the Lock

Ref

FEATURED TAGS

TOC