深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。深度优先搜索的搜索过程类似树的先序遍历，也叫回溯法。

深度优先搜索算法的基本思想

如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。在深度优先搜索中，对于当前发现的结点，如果它还存在以此结点为起点而未探测到的边，就沿此边继续搜索下去，若当结点的所有边都己被探寻过。将回溯到当前结点的父结点，继续上述的搜索过程直到所有结点都被探寻为止。

深度优先搜索在树的遍历中也称作树的先序遍历。对于树而言，深度优先搜索的思路可以描述为：

1. 将根结点置为出发结点。
2. 访问该出发结点。
3. 依次将出发结点的子结点置为新的出发结点．进行深度优先遍历(执行2）。
4. 退回上一层的出发结点。

深度优先搜索的具体编程可用递归过程或模拟递归来实现。他们各有各的优缺点。递归形式的程序符合思维习惯。编写起来较容易。但由于递归过程的调用借助较慢的系统栈空间传递参数和存放局部变量，故降低了执行效率。模拟递归使用数组存放堆栈数据，在管理指针和每层选择决策上不如递归容易编程。但一旦熟悉了程序框架，调试起来要比递归程序方便，由于数组一般使用静态内存。访问速度较快，执行效率也较高。

为了在遍历过程中区分顶点是否被访问，往往可以引入一个数组，如以mark[1..n]作为标记。数组的元素取0和1，初值为0。当节点被访问时，与节点相应得数组元素为1，每次访问节点时，都得先检查它的标记值，找0值得节点访问，并深度继续。深度大的先得到扩展，具有“后产生先扩展”的特点，因此在数据结构上采用堆栈来存储（新节点入栈，节点不能扩展时，栈定出栈）。

深度优先搜索算法的特点

1. 由于深度搜索过程中有保留已扩展节点，则不致于重复构造不必要的子树系统。
2. 深度优先搜索并不是以最快的方式搜索到解，因为若目标节点在第i层的某处，必须等到该节点左边所有子树系统搜索完毕之后，才会访问到该节点，因此，搜索效率还取决于目标节点在解答树中的位置。
3. 由于要存储所有已被扩展节点，所以需要的内存空间往往比较大。
4. 深度优先搜索所求得的是仅仅是目前第一条从起点至目标节点的树枝路径，而不是所有通向目标节点的树枝节点的路径中最短的路径。
5. 适用范围：适用于求解一条从初始节点至目标节点的可能路径的试题。若要存储所有解答路径，可以再建立其它空间，用来存储每个已求得的解。若要求得最优解，必须记下达到目前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优解，等全部搜索完成后，把保留的最优解输出。

算法描述

算法数据结构描述：

深度优先搜索时，最关键的是结点扩展（OPEN）表的生成，它是一个栈，用于存放目前搜索到待扩展的结点，当结点到达深度界限或结点不能再扩展时，栈顶结点出栈，放入CLOSE表（存放已扩展节点），继续生成新的结点入栈OPEN表，直到搜索到目标结点或OPEN栈空为止。具体算法如下：

• 把起始结点S放到非扩展结点OPEN表中(后进先出的堆栈)，如果此结点为一目标结点，则得到一个解。
• 如果OPEN为一空表，则搜索失败退出。
• 取OPEN表最前面(栈顶)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号n。
• 如果结点n的深度等于最大深度，则转向第二步。
• 否则，扩展结点n，产生其全部子结点，把它们放入OPEN表的前头(入栈)，并配上指向的n返回指针；如果没有后裔，则转向第二步。
• 如果后继结点中有任一个为目标结点，则求得一个解，成功退出；否则，转向第二步。

算法程序描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

递归过程为：
 Procedure DEF-GO(step)
 for i:=1 to max do
   if 子结点符合条件 then
     产生新的子结点入栈;
       if 子结点是目标结点 then 输出
         else DEF-GO(step+1);
           栈顶结点出栈;
        endif;
    enddo;

主程序为：
 Program DFS;
   初始状态入栈;
   DEF-GO(1);

深度优先搜索算法与广度优先搜索算法的对比图解

无向图的深度优先搜索

下面以无向图为例，来对深度优先搜索进行演示。

对上面的图G1进行深度优先遍历，从顶点A开始。

• 第1步：访问A。
• 第2步：访问(A的邻接点)C。在第1步访问A之后，接下来应该访问的是A的邻接点，即”C,D,F”中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在”D和F”的前面，因此，先访问C。
• 第3步：访问(C的邻接点)B。在第2步访问C之后，接下来应该访问C的邻接点，即”B和D”中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。
• 第4步：访问(C的邻接点)D。在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。
• 第5步：访问(A的邻接点)F。前面已经访问了A，并且访问完了”A的邻接点B的所有邻接点(包括递归的邻接点在内)”；因此，此时返回到访问A的另一个邻接点F。
• 第6步：访问(F的邻接点)G。
• 第7步：访问(G的邻接点)E。

因此访问顺序是：A -> C -> B -> D -> F -> G -> E

有向图的深度优先搜索

下面以有向图为例，来对深度优先搜索进行演示。

对上面的图G2进行深度优先遍历，从顶点A开始。

• 第1步：访问A。
• 第2步：访问B。在访问了A之后，接下来应该访问的是A的出边的另一个顶点，即顶点B。
• 第3步：访问C。在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。
• 第4步：访问E。接下来访问C的出边的另一个顶点，即顶点E。
• 第5步：访问D。接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。
• 第6步：访问F。接下应该回溯”访问A的出边的另一个顶点F”。
• 第7步：访问G。

因此访问顺序是：A -> B -> C -> E -> D -> F -> G

无向图的广度优先搜索

以无向图为例，来对广度优先搜索进行演示。还是图G1为例进行说明。

对上面的图G1进行深度优先遍历，从顶点A开始。

• 第1步：访问A。
• 第2步：依次访问C,D,F。在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在”D和F”的前面，因此，先访问C。再访问完C之后，再依次访问D,F。
• 第3步：依次访问B,G。在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。
• 第4步：访问E。在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。

因此访问顺序是：A -> C -> D -> F -> B -> G -> E

有向图的广度优先搜索

以有向图为例，来对广度优先搜索进行演示。还是以图G2为例进行说明。

对上面的图G2进行深度优先遍历，从顶点A开始。

• 第1步：访问A。
• 第2步：访问B。
• 第3步：依次访问C,E,F。在访问了B之后，接下来访问B的出边的另一个顶点，即C,E,F。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，因此会先访问C，再依次访问E,F。
• 第4步：依次访问D,G。在访问完C,E,F之后，再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。

因此访问顺序是：A -> B -> C -> E -> F -> D -> G

总结

DFS 的时间和空间分析根据其应用领域而有所不同。在理论计算机科学中，DFS通常用于遍历整个图，并且其时间Θ（| V | + | E |），[4]在图的大小上是线性的。在这些应用程序中，它还使用空间O（|V|）在最坏的情况下存储当前搜索路径上的顶点堆栈以及已经访问的顶点集合。因此，在这种情况下，时间和空间范围与广度优先搜索相同，并且选择使用这两种算法中的哪一种更少取决于它们的复杂性，更多取决于两种算法产生的顶点排序的不同性质。

对于与特定域相关的DFS应用，例如在人工智能或网络爬行中搜索解决方案，要遍历的图通常太大而无法完整访问或无限（DFS可能会因无终止而受到影响）。在这种情况下，搜索只能进行到有限的深度;由于资源有限（如内存或磁盘空间），通常不会使用数据结构来跟踪所有以前访问过的顶点的集合。当搜索被执行到有限的深度时，时间仍然是线性扩展的顶点和边的数量（尽管这个数与整个图的大小不一样，因为一些顶点可能被搜索多次，其他的根本没有），但是这种DFS变体的空间复杂度仅与深度限制成正比，因此比使用广度优先搜索搜索相同深度所需的空间小得多。对于这样的应用程序，DFS也更适合用于选择可能分支的启发式方法。如果事先并不知道适当的深度限制，迭代加深深度优先搜索重复应用DFS以增加一系列限制。在人工智能分析模式中，在分支因子大于1的情况下，由于每层级的节点数量的几何增长，迭代加深使得运行时间仅增加一个常数因子，其中正确的深度限制是已知的。

DFS也可用于收集图形节点的样本。然而，不完整的DFS，类似于不完整的BFS，被偏压向高的节点度。