BFS系列详解

转载自王琛_bfs系列详解

BFS算法基本套路

本文默认读者是有一定算法基础的，对于基本的语法和bfs概念都了解，本文由浅入深(也不是很深咯)，让你知道碰到bfs系列题目应该去怎么想，代码应该怎么去写，OK，直接进入正题。

基本bfs算法

这一部分是重中之重，因为在这里给出最基本bfs算法的写法，之后底下大部分的题，只是在这个基础上加一点东西罢了，所以这里的代码得牢记。

本文默认所有二叉树的定义如下：

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

那么最基本的，用bfs算法去遍历一颗二叉树(bfs算法基本格式，很好记)

import collections
def bfs(root):
    if not root: return
    Q = collections.deque([root])
    res=[]
    while Q:
        node = Q.popleft()
        res.append(node.val)
        if node.left: Q.append(node.left)
        if node.right: Q.append(node.right)
    return res
# [3, 9, 20, 15, 7]

或者可以写成：

def levelOrder(root):
    if not root:
        return []
    q=[root]
    res=[]
    while q:
        tmp,nq=[],[]
        for node in q:
            tmp.append(node.val)
            if node.left:
                nq.append(node.left)
            if node.right:
                nq.append(node.right)
        res.append(tmp)
        q=nq
    return res、

# [[3],[9,20],[15,7]]

以小见大，我们就从最基本的bfs算法中总结一下bfs算法的流程。

• 初始化队列，将起始点保存
• 节点依次出队列，并将出队列的节点的所有相邻节点加入队列
• 直至找到所求或队列遍历结束

bfs不仅用在树中，在二维数组（也可看成是一个图）中，也是经常使用的，正好利用上面总结的流程来看bfs算法在数组中怎么写
不妨设给定数组名为
matrix，matrix[i][j]
为起始点。

import collections
def bfs(i,j):
    m,n = len(matrix), len(matrix[0])
    visited = set((i,j))
    # 初始化队列，保存起始点
    Q = collections.deque([(i,j)])
    while Q:
        i,j = Q.popleft()
        # visited.add((x,y))
        # 所有相邻节点加入队列
        for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0<=x<m and 0<=y<n and (x,y) not in visited: # 未出界and不走回头路
                Q.append((x,y))
                # 注意visited一定要放在这里，不能是放在上面注释的地方，否则产生大量重复计算
                visited.add((x,y))

OK，基本套路在心里有个印象，然后来看两个简单例子巩固一下。

---

leetcode 107 Binary Tree Level Order Traversal

给定一棵树的根节点，按照zigzag顺序输出每层节点，即第一层节点从左至右，第二层节点从右至左，第三层节点从左至右，依次类推。

这道题和上道基本一样，无非是在处理某些层时，记录的节点顺序需要反转一下，引入一个level变量判定是否反转即可。

import collections
def bfs(root):
    if not root: return []
    Q = collections.deque([root])
    res = []
    level = 1
    while Q:
        rec = [] # record all node in the same level
        l = len(Q)
        for i in range(l):
            node = Q.popleft()
            rec.append(node.val)
            if node.left: Q.append(node.left)
            if node.right: Q.append(node.right)
        # 循环结束rec正好储存了该层的所有节点
        if level % 2 != 0: res.append(rec)
        else: res.append(rec[::-1])
        level += 1
    return res

上面两个跟树相关的bfs相对较为简单，因为对于总结的流程来说，二叉树通常有：

• 明确的起点，通常是根节点

• 明确的相邻节点且不用考虑重复遍历的情况（因为单向）

但在更多的题目中却不是这样，不论是起始点还是相邻节点，都需要我们自己去分析判断才能得出。再来看下面两个例子，感受下这类题目如何去找流程中的两个关键点。

leetcode 542 01 Matrix

给定一个矩阵matrix（只包含0or1，保证至少有一个0），返回一个矩阵res，其中res[i][j]代表距离matrix[i][j]处最近的0的距离。

对于这道题，怎么找bfs的起始点呢，我们可能最初想到的是对每一个1都进行一次bfs遍历，去寻找与他最近的0的位置，但这样显然会超时，因为当1都聚集在一起的时候会有大量重复计算。
换个思路，既然1不行，那0行吗，以单个的0肯定不行，因为这个0找到的最近的1，并不一定是最短的，还得计算别的0然后来比较，所以还是得有大量重复计算和比较。
既然起始点找单个不行，我们可以找多个，$\color{red}{我们将所有的0作为起始点}$，去找所有最后res[i][j]=1的点，$\color{red}{然后将res=1的点作为起始点}$，去找所有最后res[i][j]=2的点，以此类推。

def bfs(matrix):
    m,n = len(matrix),len(matrix[0])
    Q = collections.deque([])
    visited = set()
    # 初始化队列，将所有起始点加入
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                Q.append((i,j))
                visited.add((i,j))
    # 标准bfs写法，将相邻节点加入队列
    while Q:
        i,j = Q.popleft()
        for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0<=x<m and 0<=y<n and (x,y) not in visited:# 不出界 and 不走回头路
                matrix[x][y] = matrix[i][j] + 1
                # visited一定要在这里添加，否则产生大量重复计算
                visited.add((x,y))
                Q.append((x,y))
    return matrix

leetcode 103 Binary Tree Zigzag Level Order Traversal

给定一棵树的根节点，按照zigzag顺序输出每层节点，即第一层节点从左至右，第二层节点从右至左，第三层节点从左至右，依次类推。

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Jason
• 本文链接： https://caicaijason.github.io/2019/09/27/BFS系列详解/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！