图的广度优先遍历

图的广度优先搜索（DFS，Broad First Search），类似于一个 分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的节点的顺序，以便按这个顺序来访问这些节点的邻接节点。

算法步骤

1. 访问初始节点 v ，并标记节点 v 为已访问
2. 节点 v 入队列
3. 当队列非空时，继续执行，否则算法结束（仅对 v 的节点算法结束）。
4. 出队列，取得队头的节点 u
5. 查找节点 u 的第一个邻接节点 w
6. 若节点 u 的邻接节点 w 不存在，则跳转到步骤 3；否则执行以下三个步骤：
   1. 若节点 w 尚未被访问，则访问节点 w 并标记为已访问
   2. 节点 w 入队列
   3. 查找节点 u 的继 w 邻接节点后的下一个邻接节点 w，转到步骤 6

这里可以看到，与深度优先不同的是：

• 广度优先：找到第一个邻接节点，访问之后，会继续寻找这个节点的下一个邻接节点（非第一个）
• 深度优先：每次只找第一个邻接节点，然后以找到的节点作为基础找它的第一个邻接节点，如果找不到才回溯到上一层，寻找找它的下一个邻接节点（非第一个）

就如同上图：

• 左侧的是广度优先，先把 A 能直连的都访问完，再换下一个节点
• 右图是深度优先，每次都只访问第一个直连的节点，然后换节点继续，访问不到，则回退到上一层，找下一个直连节点