《算法图解》之广度优先搜索（BFS）

说明：以下内容均参考：[美]Aditya Bhargava所著的《算法图解》

广度优先搜索（Breadth-First Search，BFS）是一种图算法。

BFS可以计算出两样东西之间的最短距离（例如最短路径问题，解决最短路径问题的算法就被称为广度优先搜索）。

使用BFS的基本步骤：

（1）使用图来建立问题模型；

（2）使用BFS解决问题。

图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。

图用于模拟不同的东西是如何相连的。

BFS的本质是一种用于图的查找算法，它可帮助回答两类问题：

（1）从节点A出发，有前往节点B的路径吗？

（2）从节点A出发，前往节点B的哪条路径最短？

要想保证BFS找到的是最短路径，就必须要按添加顺序进行检查。如何能确保这一点呢？队列能够满足这一要求。

队列中的元素是有先后顺序的。在访问队列时，不能随机地访问队列中的某个元素。队列只支持两种操作：入队和出队。

队列是一种先进先出（First In First Out，FIFO）的数据结构，栈是一种后进先出（Last In First Out，LIFO）的数据结构。

在队列中，先加入的元素将在后加入的元素之前出队。因此，使用队列能够将图中节点之间的远近关系大致描述出来。

如何用Python构建一个最简单的图？现假设从我们出发指向了3个邻居：A、B、C，而且这3个邻居之间彼此互不相连，则借助于字典，可以将这个简单的图表示出来：

graph = {}
graph['we'] = ['A', 'B', 'C']

这样我们就完成了这个图的表示，其中的 we 被映射到了一个数组，这个数组包含了我们的所有邻居。

注意到字典中的内容是无序的，因此当需要添加多个键值对时，各键值对添加的先后顺序无关紧要。

假设一个更复杂的图如图3所示：

图3：一个更复杂的图

将这个图转换成代码如下：

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']  = []
# 各键值对的添加顺序无关紧要

像图3这样的图，只有单方向的箭头，没有反方向的箭头，这种图称为有向图。

注意邻居这一概念：箭头的终点称为箭头起点的邻居，但是箭头起点不是箭头终点的邻居。因此邻居代表了一种指向关系。在图3中，ANUJ、PEGGY、THOM以及JONNY都没有邻居，因此他们对应的映射为空。

如果有反方向的箭头，即起点和终点相互指向彼此，此时的图称为无向图，此时的两个相互指向的箭头可以合并为一条没有方向的线段（这条没有箭头的线段和两个相互指向的箭头是等价的），此时称箭头的起点和终点互为邻居。

树是一种特殊的图，特殊在树中所有的箭头都是指向同一个方向的，不存在任何反向的箭头。

针对图3的一种BFS的实现代码如下：

from collections import deque # 先从collections包中导入双向队列

class graphSearch: # class的参数表示的是继承哪种数据结构类型，可以不写
    def breadth_first_search(self, graph): # 在class中def时，第一个参数必须是self
        search_queue = deque() # 首先创建一个空的队列，用于进行BFS
        search_queue += graph['you'] # 先将you的所有邻居放在队列中，构成原始的搜索队列
        searched = [] # 这个列表用于存放已经检查过的人的名字，避免重复检查已检查过的人
        while search_queue: # 只要队列不空，就一直检查
            person = search_queue.popleft() # 每次都弹出队首元素
            if not person in searched: # 判断弹出的元素是否已经检查过了
                if self.person_is_seller(person): # 如果没有检查过，则判断他是不是芒果销售商
                    print('{} is a mango seller!'.format(person)) # 如果是，则输出信息，
                    return True # 并return
                else: # 如果这个人不是芒果销售商，就在队列的末尾添加这个人的所有邻居，
                      # 并将其标记为检查过了，以保证其不会被重复检查
                    search_queue += graph[person] # 易错：这里graph必须要用中括号去引用person！
                    searched += [person] # 易错：list相加的前提是两个对象必须都是list，
                                         # 因此person要用中括号括起来
        print('No one is a mango seller!') # 如果程序运行到这一步，则说明图中的所有节点都不是芒果销售商，
        return False                       # 此时便输出相应的信息，并return
    
    def person_is_seller(self, person): # 定义一个检查一个人是否是芒果销售商的函数，可任意定义
        if person[-1] == 'm': # 这里认为只要一个人的人名以字母m结尾，就认为这个人是芒果销售商
            return True

if __name__ == '__main__':
    graph = {} # 根据图3构建人物关系图
    graph['you'] = ['bob', 'alice', 'claire']
    graph['bob'] = ['anuj', 'peggy']
    graph['alice'] = ['peggy']
    graph['claire'] = ['thom', 'jonny']
    graph['anuj'] = []
    graph['peggy'] = []
    graph['thom'] = []
    graph['jonny'] = []
    
    result = graphSearch().breadth_first_search(graph) # 调用BFS函数

运行结果如下：

thom is a mongo seller!

这里需要注意的是，必须要有检查的步骤——对于已经检查过的人，不能重复对他进行检查，因为在某些存在环的图中，如果没有这个检查的步骤，可能会导致程序陷入死循环。

BFS的时间复杂度分析：

整个BFS可以等效为以下两步操作：

（1）将所有人都加入到队列中。由于将每个人加入队列的时间均为，因此这一步总共需要花费的时间为;

（2）沿着网络中的每条边搜索所有的人。这一步需要花费的时间取决于网络中边数的多少，因此这一步的时间复杂度为。

因此整个BFS算法的整体时间复杂度为。

通常，BFS算法的时间复杂度为，其中为顶点（vertice）数，为边（edge）数。