一?点睛
深度优先搜索是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直搜索下去，在无法搜索时，回退到刚刚访问过的节点。深度优先遍历是按照深度优先搜索方式对图进行遍历的。
深度优先遍历的秘籍：后被访问的节点，其邻接点先被访问。
根据深度优先遍历秘籍，后来者先服务，这可以借助栈实现。递归本身就是使用栈实现的，因此使用递归的方法更方便。
二?算法步骤
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