一、基本概念
1、定义
首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。
若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
2、特点
类似于树的前序遍历，尽可能先对纵深方向进行搜索。
3、基本思想
（1）访问顶点v；
（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。
4、伪代码
递归实现：
（1）访问顶点v；visited[v]=1；//算法执行前visited[n]=0
（2）w=顶点v的第一个邻接点；
（3）while（w存在）
if（w未被访问）
从顶点w出发递归执行该算法；
w=顶点v的下一个邻接点；
非递归实现：（结合栈）
（1）栈S初始化；visited[n]=0；
（2）访问顶点v；visited[v]=1；顶点v入栈S
（3）while(栈S非空)
x=栈S的顶元素(不出栈)；
if(存在并找到未被访问的x的邻接点w)
访问w；visited[w]=1；
w进栈;
else
x出栈;
5、实现
输入图像：
A
/
B C
/ /
D E F--G
/
H
程序：
N = 8 visited = [0] * N stack = [] Graphic = [[0,1,1,0,0,0,0,0],[1,0,0,1,1,0,0],[1,0,0,0,0,1,1,0],[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,1,0,0,0,1,0],[0,0,1,0,0,1,0,0],[0,0,0,1,1,0,0,0]] def unvisited(x): for v in range(N): if visited[v] == 0 and Graphic[x][v] == 1: return v return -1 for v in range(N): if visited[v] == 0: print v visited[v] = 1 stack.append(v) while len(stack) > 0: x = stack[-1] w = unvisited(x) if w != -1: print w visited[w] = 1 stack.append(w) else: stack.pop() print
二、一些定理
运行时间：O(V+E)，其中V是图中的顶点，E是图中的边。
定理一（括号定理）：解释了图中任意两点u,v在深度优先搜索森林中可能的关系
a. u是v的后裔，则[d(u),f(u)]是[d(v),f(v)]的子区间
b.v是u的后裔，则[d(v),f(v)]是[d(u),f(u)]的子区间
c.u和v完全不相交，[d(u),f(u)]与[d(v),f(v)]不相关
三、回溯与剪枝：解答树的深度优先搜索
例子：八皇后问题