图的深度优先遍历

一 点睛

深度优先搜索是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直搜索下去，在无法搜索时，回退到刚刚访问过的节点。深度优先遍历是按照深度优先搜索方式对图进行遍历的。

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

根据深度优先遍历秘籍，后来者先服务，这可以借助栈实现。递归本身就是使用栈实现的，因此使用递归的方法更方便。

二 算法步骤

1 初始化图中的所有节点都未被访问。

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

3 依次检查 v 的所有邻接点 w，如果 w 未被访问，则从 w 出发进行深度优先遍历（递归调用，重复步骤 2~3）。

三 图解

1 初始化所有节点都未被访问，visited[i] = false，i=[1,8]。

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

3 从节点1出发访问邻接点2，然后从2节点出发访问节点4，从节点4出发访问节点5，从节点5出发，没有节点再可访问。

4 回退到刚刚访问过的节点4，节点4也没有未被访问的邻接点，回退到最近访问过的节点2，从节点2出发访问下一个未被访问的邻接点6。

5 从节点6出发访问没有被访问的邻接点，回退到刚刚访问过的节点2，节点2没有被访问的邻接点，回退到最近访问过的节点1。从节点1出发访问下一个未被访问的邻接点3，从节点3出发访问节点7，从节点7出发访问节点8，从节点8出发再没被访问的邻接点。

6 回退到刚刚访问过的节点7，节点7没有未被访问的邻接点，回退到最近访问过的节点3，节点3也没有未被访问过的邻接点，回退到最近访问过的节点1，节点1也没有未被访问的邻接点，遍历结束。

深度优先遍历序列为 1 2 4 5 6 3 7 8