登机门|登机门CS 2008 |问题17

使用队列数据结构实现了广度优先搜索算法。访问下图中节点的一个可能顺序是 （A） MNOPQR （B） NQMPOR （C） QMNPRO （D） QMNPOR 答复: （C） 说明： 广度优先搜索首先访问“广度”，也就是说，如果它正在访问一个节点，那么在访问该节点之后，它将首先访问邻居节点（子节点），然后再转到下一级邻居。

让我们看看如何。

最初：如果BFS从节点Q开始，它首先访问Q并将Q放入队列。

所以，队列包含：Q。

目前的参观顺序是：Q。

现在它把Q列出来，探索它的邻居，即{M，N，P}。它会检查Q中那些尚未访问的邻居，然后访问他们，并将他们放入队列（以便以后可以访问他们的邻居）。

现在，可以访问这些邻居，并以任何顺序将其放入队列（取决于实现）。

假设它访问并按顺序（mnp）将它们放入队列中，M在前面，P在后面。

所以，访问顺序：QMNP。

现在，它寻找队列中的下一个条目。由于队列遵循先进先出原则，M将退出队列。

队列包含：（NP）

它探索M，找到它的邻居{N，Q，R}，但在访问它们之前，它会检查这些节点是否已经被访问过，它只会访问并将那些尚未访问的节点放入队列中。因为N和Q之前已经访问过，所以它只会访问R并将其排队。

访问顺序：QMNPR。 队列包含：（npr）。

邓现在排队了。

队列包含：（pr）。

它探索N，找到它的邻居{M，O，Q}。由于M和Q之前已经被访问过，所以它只会访问并进入O。

参观顺序：QMNPRO。 队列包含：（pro）。

现在，P退出队列。

队列包含：（ro）。

它探索P，找到它的邻居{O，Q}。由于O和Q之前已经访问过，所以不会排队。

现在，R退出队列。

队列包含：（O）。

它探索R，找到它的邻居{M}。因为之前已经访问过M，所以它不会排队。

现在，O退出队列。

队列包含：（）。

它探索O，找到它的邻居{N，P}。由于两人之前都去过，所以不会排队。

现在队列是空的，因此BFS在此停止。

访问顺序是：QMNPRO。

上述解释的伪代码可在 https://en.wikipedia.org/wiki/Breadth-first_search 这个问题的小测验