广度优先搜索 BFS

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 3.1k | 阅读时长 ≈ 3 分钟

「总结自《Grokking Algotithms》这本书第六章内容」

图

在 BFS（Breadth-First Search） 算法中，图是什么？

图用来模拟不同东西是如何连接的。比如，在一个游戏中，模拟谁欠谁钱。如 Alex 欠 Rama 钱，将会如下所示：

下面是多个人欠钱的情况：

可以看出图是由一系列节点（node）和边（edge）组成的。一个节点可能与多个节点直接相连接，这时候这些节点称为邻居。

广度优先算法

广度优先搜索是一种用于图的查找算法。可以帮助回答两类问题：

  • 第一类问题：从节点 A 出发，有前往节点 B 的路径吗？
  • 第二类问题：从节点 A 出发，前往节点 B 的哪条路径最短？

首先讲第一类问题。假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。首先，你需要在你的通讯录中查找，一个个查看过去，看其是否为芒果销售商。如果你的朋友中没有一个是芒果销售商，那么就从朋友的朋友中查找。

这时，检查名单中的每个人时，都将其朋友加入名单。这样一来，不仅需要在朋友中查找，还需要在朋友中的朋友中查找。使用这种算法将搜遍你的整个人际关系网，直到找到芒果销售商。这就是第一类问题的广度优先搜索。

第二类问题，就是在有路径的前提下，寻找最短距离。现在我们在刚才第一类问题的基础上，解决第二类问题 - 谁是关系最近的芒果销售商？

现在假设朋友是一度关系，朋友的朋友是二度关系，朋友的朋友的朋友是三度关系，以此类推。首次在一度关系中寻找；没有的话，再在二度关系中寻找。按照这个顺序检查名单中的每一个人，看其是否为芒果销售商。

因为，广度优先查找是从一度关系中开始查找的，整个遵从的是从最近的关系查找到最远的关系查找。所以，广度优先搜索找到的是最短的距离。

队列

因为 BFS 从最近的关系开始查找，所以对查找的名单也需要进行一定的排列。比方说，Alex 是一度关系，Rama 是二度关系。在添加列表的时候，Alex 是先加入列表的，Rama 是后就加入列表的。需要先检查 Alex，后检查 Rama，而不能先检查 Alex，后检查 Rama。有一个数据结构可以解决这个问题，就是队列（queue）。

队列的原理和排队等车的原理类似。先（早）排队的人先上车，队列也一样，是一种先进先出（First In First Out，简称 FIFO）的数据结构。

队列只支持两种操作：入队和出队。这样先加入的元素会在后加入的元素之前出队。因此队列适合 BFS 算法。

实现图

我们可以使用散列表（Hash Table）来实现图。代码如下所示：

1
2
3
4
5
6
7
8
9
10
# 实现图
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

关系如下：

实现 BFS 算法

首先概述一下整个算法的过程：

  1. 创建一个队列，用于存储要检查的人
  2. 从队列中弹出一个人
  3. 检查这个人是否是芒果销售商
  4. 判断：
    • 是芒果销售商 → 大功告成
    • 不是 → 将这个人的所有朋友加入队列
  5. 回到第 2 步
  6. 如果队列为空，则说明你的关系网中没有芒果销售商。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 实现 BFS
from collections import deque

def person_is_seller(name):
    return name[-1] == 'm'

def search(name):
    search_queue = deque() # 创建队列
    search_queue += graph[name]
    searched = [] # 用于存检查过的人
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:
            if person_is_seller(person):
                print(person + " is a mango seller")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False

完整代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
"""
广度优先算法
"""
import json

# 实现 BFS
from collections import deque

def person_is_seller(name):
    return name[-1] == 'm'

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = [] # 用于存检查过的人
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:
            if person_is_seller(person):
                print(person + " is a mango seller")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False


if __name__ == "__main__":

    # 实现图
    graph = {}
    graph["you"] = ["alice", "bob", "claire"]
    graph["bob"] = ["anuj", "peggy"]
    graph["alice"] = ["peggy"]
    graph["claire"] = ["thom", "jonny"]
    graph["anuj"] = []
    graph["peggy"] = []
    graph["thom"] = []
    graph["jonny"] = []

    print(json.dumps(graph, indent=4, separators=(',' , ':')))

    # 搜索
    search("you")