图的广度优先遍历

一 点睛

广度优先遍历又称为宽度优先搜索，是最常见的图的搜索方法之一。广度优先搜索指从某一点出发，一次性访问所有未被访问的邻节点，再依次从这些已访问过的邻接点出发，一层一层地访问。广度优先遍历是按照广度优先搜索的方式对图进行遍历的。

按照广度优先搜索的顺序，上图的访问顺序是：1 2 3 4 5 6

广度优先遍历的秘籍：先被访问的节点，其邻节点先被访问。

根据广度优先遍历的秘籍，先来先服务，可以借助队列实现。因为对每个节点只访问一次，所以可以设置一个辅助数组 visited[i] = false，表示第 i 个节点未被访问；visited[i] = true，表示第 i 个节点已被访问。

二 算法步骤

1 初始化所有节点均为被访问，并初始化一个空队列。

2 从图中的某个节点 v 出发，访问 v 并标记其已被访问，将 v 入队。

3 如果队列非空，则继续执行，否则算法结束。

4 将队头元素 v 出队，依次访问 v 的所有未被访问的邻接点，标记已被访问并入队，转向步骤3.

三 图解

一个有向图如下图所示，其广度优先遍历的过程如下所述。

1 初始化所有节点都未被访问，visited[i] = false，i =[1,6]。并初始化一个空队列 Q。

2 从节点 1 出发，标记其已被访问，visited[1] = true，将节点 1 入队。

3 将队头元素 1 出队，依次访问 1 的所有未被访问的邻接点2和3，标记其已被访问并入队。

4 对队头元素2出队，将2未被访问的邻接点4标记为已被访问，并将其入队。

5 将队头元素3出队，3的邻接点2已被访问，不用处理，将未被访问的邻接点5标记为已被访问，并将其入队。

6  将队头元素4出队，4的邻接点3已被访问，不用处理，将未被访问的邻接点6标记为已被访问，并将其入队。

7 将队头元素5出队，5 的邻节点4和6已被访问，不用处理，没有未被访问的邻接点。

8 将队头元素6出队，6没有邻接点。

9 队列为空，算法结束。广度优先遍历序列为 1 2 3 4 5 6。