Day 18：广度优先搜寻(BFS)

上一回提到广度优先搜寻的步骤是检查图中节点，并将与其相连的节点放入伫列中，再一一检查。

光是这样的文字描述，可能感觉只是线性地检查所有节点，但其实广度优先搜寻的重点在於它是从一个节点开始，放射状、逐层向外的搜寻。

从起始的节点开始，它所有邻居(neighbors，指相邻的节点)算是第一层，要先搜寻完第一层所有的节点後，才开始搜寻邻居的邻居，也就是第二层的节点，所以整个搜寻会从起点向外层层扩展。

如果不是这样一层一层搜寻，就可能会出现内层还没搜寻完，就搜寻外层的错误，这样会造成什麽问题呢？

假设毛豆同学今天忘了带立可带，想要跟同学借，并且希望能借他的同学座位离他越近越好。所以毛豆就从跟他座位直接相连的前、後、左、右四位同学问起。如果这四位同学都没有，他们再跟他们的前後左右的同学询问。

如果毛豆问完右边的A同学，A同学没等毛豆问其他人，就立马再问他右边的Q同学，发现Q同学有立可带。可是其实毛豆左边的B同学就有立可带，但因为先问了第二层的同学，所以最终虽然有借到立可带，但并不是距离毛豆最近的选项。

也就是说，如果不是第一层的邻居搜寻完再搜寻第二层，可能发生找到的路径并非最短路径的问题。为了要避免这种情况，我们要利用伫列(queue)这种结构。

伫列是一种线性的资料结构。它的名称queue也是排队的意思，现实生活中在排队结帐时，先开始排的人会先结帐离开，想要排队只能从队伍最後排起。

资料结构的伫列跟排队一模一样，资料从前端删除，後端加入，所以先加入的资料一定会先删除。跟同样是线性结构的堆叠相比，伫列是先进先出(FIFO)的资料结构；堆叠则是後进先出(LIFO)。

先进先出的这个特性，就确保了广度优先搜寻会找到正确答案。

今天毛豆想要借立可带的第一步，就是先将他四周的ABCD同学加入伫列中，问了A同学发现没有，就把A同学的邻居OPQ同学加入伫列中，也就是排队在BCD之後。因为伫列运作的方式，一定会先检查完BCD才会轮到後面加入的同学，所以绝对不会出现坐比较远的同学先被询问的情况。

除了搜寻顺序外，操作广度优先搜寻时我们可能还会碰到另一个问题，就是把已经检查过的节点又加入了伫列。

例如当毛豆问完A同学後，就要把A同学的邻居加入伫列，可是这麽做的时候又会把毛豆算进去，因为他们互为邻居，会不断把对方加入伫列。

当发生这样的情形时，不但会浪费资源搜寻已经检查过的节点，而且搜寻会陷入无限回圈。所以通常会用一些方式来标示已经检查过的节点，例如将检查过的节点存入一阵列，以避免重复检查。

广度优先搜寻是一种会彻底搜寻整张图的演算法，最坏情况得经过每个边并检查每个节点，所以执行时间是O(|V|+|E|)，其中|V|是节点的数目，|E|是边的数目。