一、定义

深度优先搜索是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等。深度优先搜索算法最早是由Tarjan(1972)发表的，该算法采用递归调用，代码简洁高效，也是针对大规模网络中各种动态拓展研究中最常采用的算法。

搜索的本质其实就是试探问题的所有可能性，在遍历的过程中，最重要的规则即为不重不漏，最经典的深度优先搜索遵循了这个规则。

深度优先搜索，也是一种回溯法，从根开始计算，到找到位于某个结点的解，其采用了一种“一直向下走，走不通就掉头”的思想（体会“回溯”二字），相当于采用了先根遍历的方法来构造搜索树。

DFS算法是以遍历所有结点为主要目的的算法，它不一定能遍历所有的路径。

在搜索算法中，深度优先搜索（也可以称为回溯法）是搜索算法里最简单也最常见的。

二、基本思想

深度优先遍历图的方法是，从图中某顶点v出发：

（1）访问顶点v；

（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

三、Tremaux搜索

Tremaux搜索是探索迷宫而不迷路的一种古老办法。其实走迷宫，和搜索图是一样的。我们只需要把迷宫看成图，迷宫里的通道看成边，岔路口和拐角处看成顶点，探索迷宫其实就是搜索一个图。

例子1 通道迷宫

图3-1

1. 理解图3-1

(1) 左上角是迷宫，由通道组成。

(2) 左下角是从迷宫抽象出来的图，直线代表通道，两通道相遇的地方代表两直线的交点。

(3) 右边代表搜索通道的过程，红线代表搜索的路径，很浅的灰线代表回退的路径（当前进中遇到已经搜索过的点时，回退，直到回退到的点可以从新的路径继续开始搜索）。

(4) 也可以反过来理解，将图看成迷宫，通道代替边，路口代替顶点,是在思考图的搜索过程中一种有益的方法。

2. 总结搜索方法如下：

(1) 选择一条没有标记过的通道，在你走过的路上铺一条绳子；

(2) 标记所有你第一次路过的路口和通道；

(3) 当来到一个标记过的路口时（用绳子）回退到上个路口；

(4) 当回退到的路口已没有可走的通道时继续回退。 当回退的路口有新的通道（即没有标记过的通道时），从新的通道继续走。

绳子可以保证你总能找到一条出路，标记则保证你不会两次经过同一条通道或者同一个路口。

例子2 表格迷宫

起点为（1,1），找到所有的到（4,4）的路径。如图3-2所示。

图3-2

首先抽象出图，按照深度优先搜索找到所有路径，可以找到两条路径：A-B-D-E; A-B-C-E。如图3-3所示。

图3-3

四、深度优先搜索可以实现穷举

现实生活中，很多问题我们不能够找出确切的数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，也有可能找不到问题的解，试探时一定要试探完所有的情况，实际上就是穷举。

五、堆栈（stack）实现

DFS使用计算机数据结构---堆栈(stack)来实施算法过程，堆栈有着后进先出LIFO(Last In First Out)的特性。DFS对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。

六、演示例子

对于图6-1的树而言，DFS方法首先从根结点1开始，其搜索结点顺序是1、2、3、4

5、6、7、8、9（假定左分枝和右分枝中优先选择左分枝）。

图-6-1

DFS操作步骤如下：

（1）选一个根结点1，将结点1放入右边堆栈的栈底。如图6-2所示。

图6-2

（2）找出与结点1邻接的且尚未遍历的一个结点2（注意只选择一个结点，另一个相邻结点8先不管它），进行标记，然后放入右边的stack中。如图6-3所示。

图6-3

（3）重复（2）的动作，直到某一个结点没有尚未遍历的邻接点为止，如结点5已经没有尚未遍历的邻接点了。如图6-4所示。

6-4

（4）如果结点搜索发现已经没有尚未遍历的邻接点了，则将此结点从栈顶弹出。例如，从5搜索到2时，发现2是已经访问过的结点，回退（专业术语是将结点5出栈）。如图6-5所示。

图6-5

（5）重复（4），不断回退，直接发现结点有另外的没有做标记的邻接点为止。例如，结点4又找到了没有做过标记的新的邻接点6，停止回退，同时将结点6入栈。如图6-6所示。

图6-6

（6）找到新结点7， 将结点7入栈。

图6-7

（7）结点7没有尚未遍历的邻接点，弹出结点7，找到新结点8，将结点8入栈；再找到新结点9，将结点9入栈。直到遍历完整棵树。

图6-8

（8）最后搜索完后没有新的结点，一步一步回退，即全部出栈，最后栈为空，DFS遍历完成。

图6-9

小结：

深度优先搜索结点被搜索到的顺序是不确定，图示中只是给出了一种可能的情况。但是无论结果中结点的顺序如何，都要遵循着从最近发现的结点出发深入搜索的原则。如果结点有多个邻接点，选择邻接点的顺序不同，就会有不同的深度搜索序列。

本例遍历的结果可以有很多种：1-2-3-4-5-6-7-8-9；1-8-9-6-7-4-5-2-1-3；1-8-9-6-7-4-5-2-3-1等。

如果我们按照从左到右的搜索顺序，就只有一种结果了：1-2-3-4-5-6-7-8-9。

用到了c语言中的数据结构---堆栈(stack) 的概念，抽空了解一下。

七、深度优先搜索的优缺点

优点：

能找出所有解决方案； 优先搜索一棵子树，然后是另一棵，所以和广度优先搜索相比，内存需要相对较少的优点。

缺点：

要多次遍历，每个结点访问需要回溯，访问不止一次， 搜索所有可能路径；在深度很大的情况下效率不高。八、应用案例1 教授穿衣

图8-1描述的是Bumstead教授每天早上起床穿衣所发生的事件的次序图。教授必须先穿某些衣服，才能再穿其它衣服(如先穿袜子才能再穿鞋)。有些服饰可以任意顺序穿上(如袜子与裤子之间可以以任意次序进行穿戴)。图(a)所示的有向无环图中，有向边(u,v)表明服饰u必须在服装v之前穿上。对该有向无环图进行拓扑排序所获得的就是一种合理穿衣的次序。图(b)将拓扑排序后的有向无环图在一水平线上展现出来，在该水平线上，所有的有向边都从左指向右。

解答：我们的办法是使用深度优先搜索来对有向无环图进行拓扑排序。

深度优先搜索的发现时间和完成时间的时间顺序也就是结点搜索与回溯的时间顺序。

(1) 搜索衬衣1---搜索领带2---搜索夹克3---回溯夹克4---回溯领带5--搜索腰带6---回溯腰带7---回溯衬衣8

(2) 搜索手表9---回溯手表10

(3) 搜索内裤11---搜索裤子12---搜索鞋13---回溯鞋14---回溯裤子15---回溯内裤16

(4) 搜索袜子17---搜索鞋---回溯鞋---回溯袜子18

图(a) 在每个结点旁边都标记有发现时间/完成时间。

图(b)是按照结点完成时间(回溯时间)的顺序来进行拓扑排序的。

图8-1

案例2 开发爬虫

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超级链接的HTML文件) 。在一个HTML文件中，当一个超级链接被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超级链接走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超级链接。当不再有其它超级链接可选择时，说明搜索已经结束。

其它案例

深度优先搜索有许多广泛的应用，例如人工智能、导弹航迹规划、城市道路规划等。一句话，能抽象成图或树的场景都有可能用到深度优先搜索。

九、附录附录1

拓扑排序的理论研究最早在项目管理日程安排中的计划评审技术(PERT: Program Evaluation and Review Technique )的相关背景下出现(Jarnagin 1960)。拓扑排序算法最早则是由Kahn(1962)提出来的。在计算机科学中，这种类型的应用也出现在计算机指令调度，电子表格中在重新计算公式值时的公式单元评价结果的排序，逻辑综合，执行编译文中的编译任务的顺序的测定和串行化以及在连接器中的符号依赖关系的解析等。

拓扑排序是图G中所有结点的一种线性次序，该次序满足如下条件：如果图G包含边（u，v），则结点u在拓扑排序中处于结点v的前面（如果图G包含环路，则不可能排出一个线性次序）。

如图9-1所示，事件E1完成之后，可以同时执行事件E2和E3，两事件执行结束之后，执行事件E4，最后可以同时执行事件E5和E6。每个事件的执行都依赖于它之前事件是否执行完成，执行的顺序是固定的，这样的线性顺序就是拓扑排序。

图9-1

拓扑序列是有向无环图的顶点的一个线性序列，只有有向无环图才具有拓扑序列。

拓扑排序的基本算法有3种：源点消去算法、广度优先搜索算法、深度优先搜索算法。