广度优先搜索为什么选择队列来存储

队列这种数据结构是广度优先搜索算法优先选择的数据结构。第一是因为队列的存储机制为先进先出,而广度优先搜索算法恰好需要保证优先访问已访问顶点的未访问邻接点。因此队列最适合广度优先算法的存储法则。

选择队列存储结构的第二个原因是,队列这种数据结构只支持两个基本操作:将新元素从队尾加入队列和将队首元素移出队列。相比于其他数据结构(如数组等),队列因为操作简单而效率高。

但队列也因为只有两个基本操作而使得一些特殊操作十分复杂:如通过循环遍历在队列中查找某个特定的元素。幸运的是,广度优先搜索算法并不需要循环遍历其存储元素的数据结构,所以队列即广度优先算法的不二之选。

对于 Python 语言来说,可以通过列表来模拟队列,通过 append() 函数来将新元素插入队列和 del() 函数来删除队首元素,也可以通过调用 Python 标准库 queue 来实现队列结构,通过 put() 函数插入新元素和 get() 函数提取并删除队首元素。

用一个二叉树图结构来举例,如图 1 所示。
二叉树示例
图 1:二叉树示例

图 1 所示为一棵二叉树。这时如果我们规定若要访问一个节点则必须访问其根节点,就可以运用广度优先搜索算法来实现图 1 所示二叉树的遍历。

遍历之前,我们需先定义一个队列结构,用来存储即将遍历的节点。对于这个二叉树来说,其根节点(1 号节点)是必须首先遍历的,因此我们在初始化时将根节点加入队列。现在队列状态如图 2 所示。
初始化队列的状态
图 2:初始化队列的状态

现在队列中只有一个元素:根节点。为了将其他节点加入队列中,我们需访问队列中最前面的元素,并将其移出队列,来确定即将被加入队列的元素,更新队列。对于二叉树来说,需将根节点1移出队列,并通过该节点来找到其子节点:节点2和节点3,并加入队列之中。操作如图 3 和图 4 所示。
队列首项被移出队列
图 3:队列首项被移出队列

新节点加入队列
图 4:新节点加入队列

之后,我们只需要按照之前的操作依次移出队首的元素,并将队首元素节点的子节点加入队列中,反复运行直到队列为空为止,即可完成遍历,如图 5~图 11 所示。
队列操作(1)
图 5:队列操作(1)
队列操作(2)
图 6:队列操作(2)
队列操作(3)
图 7:队列操作(3)
队列操作(4)
图 8:队列操作(4)
队列操作(5)
图 9:队列操作(5)
队列操作(6)
图 10:队列操作(6)
队列操作(7)
图 11:队列操作(7)