vlambda博客
学习文章列表

你好，我是悦创。好久不见，但我想在我每次回来的时候给你分享绝对的干货，这种文章注定不会想那种营销号那样吸引朋友们的眼球，但我的文章绝对能或多或少的帮助到你，如果绝对有帮助，可以转发给周围的小伙伴。

这里我说个题外话，有喜欢摄影的小伙伴，可以加我好友拉你进摄影交流群和我免费分享的手机摄影课程和相机摄影课程哦。我们终将再另有一个空间相遇。

深度优先遍历算法是经典的图论算法，深度优先遍历算法的搜索逻辑和它的名字一样，只要有可能，就尽量深入搜索，直到找到答案，或者尝试了所有可能后确定没有解。

什么是深度优先遍历？

首先，我们来看一下什么是深度优先遍历。

举一个最简单而抽象的例子 —— 走迷宫。走迷宫等搜索问题可以追溯到古希腊时代。甚至现在还流传着一个走迷宫的传说，是关于米诺陶洛斯和忒修斯的希腊故事。

传说由于米诺斯的儿子被雅典人阴谋杀害，米诺斯起兵为儿子报仇，给那里的居民造成很大的灾难，为了平息米诺斯的愤恨，解除雅典的灾难，雅典人向米诺斯求和，答应每九年送七对童男童女到克里特作为进贡，米诺斯接到童男童女后，将他们关进半人半牛怪米诺陶洛斯居住的克里特迷宫里，由米诺陶洛斯把他们杀死。

在第三次进贡的时候，年轻的忒修斯带着选中的男孩女孩向爱情女神阿佛洛狄忒献礼并祈求护送，结果克里特的公主阿里阿德涅爱上了忒修斯，给了他一个线团，叫他把线的一头栓在迷宫入口，一直牵着线走入迷宫，找到怪物米诺陶洛斯藏身的地方。同时还给了他一把能杀死米诺陶洛斯的剑。忒修斯和贡品都被送进迷宫，忒修斯杀死了弥诺陶洛斯并成功靠线团走出了迷宫。最后忒修斯就带着阿里阿德涅顺利离开了克里特。

这种方法称为深度优先搜索（DFS）。总结起来，深度优先算法的本质是以遍历的深度为最优先的因素进行搜索。就好像 “一条路走到黑”，直到不能走才回到上一个分岔路口换另一条路，有点 “不撞南墙不回头” 的意思。

搜索算法里的搜索和平时我们生活中搜索引擎中的搜索不尽相同，后者的意思更趋近于 “寻找”，即在互联网的海量信息中寻找带有关键字的有用信息。而前者的意思则是 “遍历”，通俗的来讲，就是以一定的算法为基础和判断标准，不重不漏地访问每一个元素。因此，搜索算法又可以被称为遍历算法。搜索的本质其实就是试探问题的所有可能性，并按照特定的规律和顺序，持续地去遍历每一种可能，直到找到问题的解。如果把所有可能都遍历了一遍，也没有找到解，就说明这个问题可能不存在一个完美的解。

在遍历的过程中，最重要的原则即为不重不漏，所以我们要在搜索（遍历）的过程中制定一系列有效的规则来保证这一需求。为了保证不重不漏，最经典的两个规则就是深度优先和广度优先。

搜索问题的本质就是试探问题的所有可能选择，按照特定的规律和顺序，不断地去搜索答案，直到找到问题的解。如果把所有可能都走了一遍，也没有找到解，就说明这个问题没有解。

注意：深度优先遍历问题一定要按照规则尝试所有的可能才行.

深度优先遍历算法是经典的图论算法，从某个节点 v 出发开始进行搜索，不断搜索直到该节点的所有边都被遍历完。当节点 v 的所有边都被遍历以后，深度优先遍历算法则需要回溯到 v 的前驱节点，来继续搜索这个前驱节点的其他边。

如果还存在尚未被遍历的节点，则深度优先遍历算法将会按照统一的规则从这些剩下的节点中选择一个节点再重复同样的遍历过程。这样的搜索过程从最开始的节点一直持续到最后一个节点的所有边都遍历完。

为了有效地提取图的有用信息，我们往往使用循环来遍历每一个顶点和边，从而获取一个图的某些简单性质（例如一个图的所有顶点的度数，或者所有边加起来的长度）。但通过以任意顺序遍历每条边来分析一个图这样的方法很简单也很便利，其所能提取的信息和性质往往也会价值比较低。但一个图常常有一些复杂的性质是简单循环遍历无法得出的，比如说判断一个图是否为二叉树，或是否能从一个顶点通过连接的边从而到达另一个顶点等等。在这些复杂性质中，凡是跟路径或转移（从一个顶点到另一个顶点）相关的问题，往往都需要用搜索来解决。

之后，我们来看几个深度优先搜索算法的问题。

划重点

深度优先搜索算法是经典的图论算法，深度优先遍历算法的搜索逻辑和它的名字一样，只要有可能，就尽量深入搜索，直到找到答案，或者尝试了所有可能后确定没有解。