概念

从图中某一顶点出发访问图中其余顶点，且使每个顶点都被访问且仅被访问一次，这个过程叫做图的遍历。图的遍历方式有两种：深度优先和广度优先。

深度优先

深度优先（Depth First Search）的策略是从初始访问结点出发，初始结点可能有多个邻接点，优先访问第一个邻接结点，然后再以被访问的邻接结点作为初始结点，访问它的第一个邻接结点。这样的访问策略是优先往纵向深入挖掘，而不是对每一个结点的所有邻接结点进行横向访问。

深度优先遍历的步骤：

1. 访问初始结点 v，并标记结点 v 为已访问。
2. 查找 v 的第一个邻接结点 w。
3. 若 w 存在，则继续执行下一步；若 w 不存在，则回到第一步，从 v 的下一个结点作为 w 出发。
4. 若 w 未被访问，对 w 进行深度优先遍历（递归执行步骤 1、2、3）。
5. 查找结点 v 的 w 邻接结点的下一个邻接结点，转到步骤 3。

广度优先

广度优先（Broad First Search）的策略是从初始访问结点出发，访问完初始结点的所有邻接结点之后再选择下一个邻接结点作为初始结点，再访问该初始结点的其它邻接结点。广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。

广度优先遍历的步骤：

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