弄懂难缠的BFS算法和相关变种(Python实现)

字数统计: 1.6k   |   阅读时长≈ 6 分钟

前言

这段时间频繁刷题，leetcode真的好难啊！！每次都他娘的做不出来，除了刷题，最近还在复习各种架构，或者是完成公司的开发。这些占据了我过多时间，所以blog其实一直想写，但是实在腾不出时间，今天在针对性刷leetcode的时候，对BFS/DFS有了一点别的感悟，所以就写一篇博客，作为自己的笔记，在记录的同时，也帮助其他兄弟少走弯路，希望，能够帮到大家。

什么是BFS算法？

这些百度谷歌都搜的到，不过这里还是简单说一下吧

首先，BFS的全名，叫做广度优先搜索算法

搜索，顾名思义，是找寻某个东西，所以叫搜索，在写代码的时候，搜索，其实等同遍历，只是这个遍历是有条件的。

相对于BFS，它的条件是什么呢？

举个例子，有个迷宫，有两个点，你要从A 移动到 B，中间带X的表示墙壁，无法通行

1
2
3
4
5
A 0 0 0 

X 0 0 X

0 X 0 B

现在走出第一步

1
2
3
4
5
A 1 0 0 

X 0 0 X

0 X 0 B

走现在走第二步，发现有两个可以走的地方（分岔路）

1
2
3
4
5
A 1 2 0 

X 2 0 X

0 X 0 B

走第三步，依旧有个分岔路

1
2
3
4
5
A 1 2 3 

X 2 3 X

0 X 0 B

走第四步，只有一条路

1
2
3
4
5
A 1 2 3 

X 2 3 X

0 X 4 B

第五步，走到B点

1
2
3
4
5
A 1 2 3 

X 2 3 X

0 X 4 B

我们画出可行的步骤

1
2
3
4
5
A-1-2 3 
  | |
X 2-3 X
    |
0 X 4-B

BFS（广度优先）算法，就是记录所有可行的路径。

当面临选择和岔路的时候，BFS选择我全都要，全都记录下来，然后选择其中一个进入，如果有死路，它选择返回，选另外的岔路，继续重复这样的操作。

可以看出，BFS是逐步求解的，由近到远。这里找路程的步骤，用动态图来展示如下

这个图其实就直接说明了BFS算法的特点

这个图真的很棒！我一看就大概明白BFS算法了。
感谢此图的作者，如果你看到，请联系我，我会加上你的名字作为引用！谢谢！

是不是很像钢铁雄心4推进部队的样子？

持续性突进！

树的BFS算法

前面你可以看到，BFS算法，其实就是将分支逐步列出。

其实对于树这个结构来说，BFS算法更像是特殊的遍历整个树结构的一种方法。

举个例子

假设我们弄一个树

1
2
3
4
5
     A
   /   \
  B     C
 / \   / \
D   E F   G

一般的遍历逻辑就是(前序遍历)

A - B - D - E - C - F - G

但是，BFS可不是这么玩的，BFS的遍历逻辑就是
A - B - C - D - E - F - G

这里来个图，你一看就明白！

这就是树的BFS遍历，其实说起来也没多难吧？

树的BFS算法模版

根据上面的逻辑，我们可以看出来，树的BFS算法是一层层的层次搜索算法，并且是先进先出的逻辑。

如图所示

那么，遍历树的BFS的模版，应该这么写

首先，定义一个树的结构体

1
2
3
4
5
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

由于先进先出的结构特点，这里使用队列来进行存储数据，这是因为BFS算法需要保证优先访问顶点的未访问领接点。

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

def BFS(root):
    if root == None:
        return

    # 队列化root
    queue = deque([root])

    result = []

    # 遍历root
    while queue:
        # 移去并且返回一个元素，queue 最左侧的那一个
        node = queue.popleft()
        # 获取node的详细情况
        result.append(node.val)
        print(node.val)
        # 访问左树
        left = node.left
        if left != None:
            queue.append(left)
        # 访问右树
        right = node.right
        if right != None:
            queue.append(right)
    return result

写一个测试的方法，就按着我们刚刚那个A - G的树来一把

1
2
3
4
5
6
7
8
9
if __name__ == "__main__":
    tree = TreeNode("A")
    tree.left = TreeNode("B")
    tree.right = TreeNode("C")
    tree.left.left = TreeNode("D")
    tree.right.right = TreeNode("E")
    tree.right.right.right = TreeNode("F")
    tree.right.right.right = TreeNode("F")
    print(BFS(tree))

打印出来

1
2
3
4
5
6
7
A
B
C
D
E
F
['A', 'B', 'C', 'D', 'E', 'F']

树的BFS算法变种

从上到下打印二叉树 III

leetcode地址：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

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
27
请实现一个函数按照之字形顺序打印二叉树，

即第一行按照从左到右的顺序打印，

第二层按照从右到左的顺序打印，

第三行再按照从左到右的顺序打印，其他行以此类推。

 

例如:
给定二叉树: 

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

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

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

分析题目

这道题，主要就是用BFS去做遍历，然后遍历的同时判断现在遍历到第几层，然后根据层数转换打印的次序，这道题不算太难

首先先写个BFS模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
queue = deque([root])

result = []

while queue:
    node = queue.popleft()
    result.append(node.val)
    print(node.val)
    left = node.left
    if left != None:
        queue.append(left)
    right = node.right
    if right != None:
        queue.append(right)

return result

根据需求，首先先解决输出是

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

的问题，其实说明内部嵌套多个队列，改写一下，当遍历每一层的时候，添加到新的队列当中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while queue:
    # 定义一个新的队列
    tmp = deque()
    # 判断队列循环到哪里
    for i in range(len(queue)):
        node = queue.popleft()
        # tmp 队列 添加 val数据
        tmp.append(node.val)
        left = node.left
        if left != None:
            queue.append(left)
        right = node.right
        if right != None:
            queue.append(right)
    result.append(list(tmp))
return result

接下来就要判断循环的行号是偶数还是计数

1
2
3
4
5
6
# 如果是偶数
if len(result) % 2:
    # 添加到队列左端
    tmp.appendleft(node.val)
else:
    tmp.append(node.val)

最终的代码是

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
27
28
29
30
31
from collections import deque

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

def BFS(root):
    if root == None:
        return []

    queue = deque([root])

    result = []

    while queue:
        tmp = deque()
        for i in range(len(queue)):
            print(len(result))
            node = queue.popleft()
            if len(result) % 2:
                tmp.appendleft(node.val)
            else:
                tmp.append(node.val)
            if node.left != None:
                queue.append(node.left)
            if node.right != None:
                queue.append(node.right)
        result.append(list(tmp))
    return result

结尾

我这里只总结了二叉树的几个题目，其实还不是很全，最近实在是太忙啦！后面会补全图算法的BFS和DFS算法，大家多多期待吧！

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • © 2019-2022 Yemilice lau
  • Powered by Hexo Theme Ayer
  • PV: UV:

觉得帮到你了么？赏我点儿~

支付宝
微信