图 - 图的遍历（下）—— 广度优先搜索
- 3 mins数据结构与算法系列（四十六）
上篇文章我们分享了通过深度优先搜索对图进行遍历，这篇我们来探讨如何通过广度优先搜索对图进行遍历。
广度优先搜索定义
广度优先搜索（Breadth First Search），简称 BFS，我们以在家里房间里找钥匙为例来对比说明深度优先搜索和广度优先搜索，深度优先搜索好比我们从某个房间（顶点）开始，先把一个房间的所有角落找遍，再从下一个相邻房间开始继续找，依次类推，但这有时候并不是最佳方案，我们可以换一种思路，先大致扫一下每个房间的常见位置，如果都没有的话才继续更深入的寻找，这种遍历方式就是广度优先搜索。
还可以通过树的遍历来类比图的遍历，前序遍历类似深度优先搜索，层序遍历类似广度优先搜索，下面我们以一个图为例来说明，这样更加形象：
左图是我们要遍历的图，右图是以广度优先搜索对图进行遍历，我们把 A 作为第一层，B、F 作为第二层，C、I、G、E 看作第三层，D、H 看作第四层，每次遍历一层。
这与我们上一篇讲述的深度优先搜索显然不同，深度优先搜索会把某个顶点的所有相邻顶点访问完才继续下一个顶点的访问，广度优先搜索则不然，它是按照「层级」遍历图的节点，最终也能够遍历完所有节点。
广度优先搜索实现
下面我们把上述广度优先搜索的实现转化为代码实现，我们还是基于上篇文章定义的 Graph 类，为其编写广度优先搜索实现方法。
在实现广度优先搜索的时候需要用到队列的概念，我们访问到某个顶点时，将其相邻顶点推送到队列中，然后访问完一层之后，根据队列先入先出的特点，从该层顶点相邻顶点中取出最先插入的顶点，即下一层的第一个顶点开始进行访问，这样，依次类推，就完成了广度优先搜索。
为此我们还要实现一个简单的队列实现（参考我们在队列一节中的实现）：
/**
* 通过 PHP 数组实现的队列
*/
class SimpleQueue
{
private $_queue = [];
private $_size = 0;
public function __construct($size = 10)
{
$this->_size = $size;
}
// 入队
public function enqueue($value)
{
if (count($this->queue) > $this->size) {
return false;
}
array_push($this->_queue, $value);
}
// 出队
public function dequeue()
{
if (count($this->_queue) == 0) {
return false;
}
return array_shift($this->_queue);
}
public function size()
{
return count($this->_queue);
}
}
然后，我们在 Graph 类中实现广度优先搜索方法 bfs 如下：
public function bfs($s, $t)
{
if ($s == $t) {
return;
}
for ($i = 0; $i <= $this->v; $i++) {
$visited[$i] = 0;
}
$queue = new SimpleQueue();
$queue->enqueue($s);
for ($i = 0; $i <= $this->v; $i++) {
$prev[$i] = -1;
}
while ($queue->size() > 0) {
$w = $queue->dequeue();
for ($i = 0; $i < $this->adj[$w]->getSize(); $i++) {
$q = $this->adj[$w]->get($i)->data;
if (!$visited[$q]) {
$prev[$q] = $w;
if ($q == $t) { // 找到了
$this->printPath($prev, $s, $q);
return;
}
$visited[$q] = 1;
$queue->enqueue($q);
}
}
}
}
visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q] 会被设置为 true。
queue 是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，我们只有把第 k 层的顶点都访问完成之后，才能访问第 k+1 层的顶点。当我们访问到第 k 层的顶点的时候，我们需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以，我们用这个队列来实现记录的功能。
prev 用来记录搜索路径。当我们从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存储的就是搜索的路径。不过，这个路径是反向存储的。prev[w] 存储的是，顶点 w 是从哪个前驱顶点遍历过来的。比如，我们通过顶点 2 的邻接表访问到顶点 3，那 prev[3] 就等于 2。
广度优先搜索的时间复杂度和深度优先搜索一样，也是 O(v+e)，其中 v 表示顶点数，e 表示边数，需要额外的数组存储已访问顶点和前驱顶点，对应的空间复杂度是 O(v)。
广度优先搜索和深度优先搜索的复杂度完全一样，没有优劣之分，具体使用哪种搜索方式，以实际情况为准。