广度优先搜索 BFS
「总结自《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）来实现图。代码如下所示：
# 实现图
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 算法
首先概述一下整个算法的过程：
- 创建一个队列，用于存储要检查的人
- 从队列中弹出一个人
- 检查这个人是否是芒果销售商
- 判断：
- 是芒果销售商 → 大功告成
- 不是 → 将这个人的所有朋友加入队列
- 回到第 2 步
- 如果队列为空，则说明你的关系网中没有芒果销售商。
代码实现：
# 实现 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完整代码
"""
广度优先算法
"""
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")