深度优先搜索(DFS)
深度优先搜索(DFS)是一个算法搜索一个图或树数据结构。该算法从树的根(顶)节点开始,沿着给定的分支(路径)尽可能深入,然后回溯,直到找到一个未探索的路径,然后探索它。算法一直这样做,直到整个图被探索。计算机科学中的许多问题都可以用图来思考。例如,分析网络、绘制路线、调度和查找生成树图问题。为了分析这些问题,图搜索算法像深度优先搜索是有用的。
深度优先搜索通常被用作其他更复杂算法的子程序。例如,匹配算法,Hopcroft-Karp,使用DFS作为其算法的一部分来帮助找到匹配在一个图。DFS也用于树遍历算法,也被称为树搜索,它在旅行推销员问题和Ford-Fulkerson算法.
你如何解决一个迷宫?
深度优先搜索是许多人解决迷宫之类问题的常见方法。首先,我们在迷宫中选择一条路径(游戏邦注:让我们根据预先设定的规则选择一条路径),然后沿着它走下去,直到到达一个死胡同或到达迷宫的终点。如果给定的路径不起作用,我们就返回,从过去的交叉路口选择另一条路径,并尝试那条路径。下面是解决这个迷宫的DFS方法的动画。
深度优先搜索
深度优先搜索的主要策略是尽可能深入地探索图。深度优先搜索探索的是最近发现的顶点的边缘, .只有指向未探索顶点的边才会被探索。当所有的 的边缘已经被探索过了,搜索就会回溯,直到到达一个未被探索过的邻居。这个过程将继续进行,直到发现所有可以从原始源顶点到达的顶点为止。如果有未访问的顶点,深度优先搜索将选择其中一个作为新来源,并从该顶点重复搜索。算法重复整个过程,直到发现每个顶点。这个算法很小心,不会重复顶点,所以每个顶点只探索一次。DFS使用堆栈跟踪顶点的数据结构。
以下是执行深度优先搜索的基本步骤:
- 访问一个顶点 .
- 马克 参观了。
- 递归访问每个未访问的顶点 .
这个动画演示了深度优先搜索算法:
注意:此动画没有显示节点的标记为“已访问”,这将更清楚地说明回溯步骤。
根据深度优先搜索访问节点的顺序,将每个节点1 ~ 12标记为如下图所示:
解决方案:
实现深度优先搜索
下面是递归和非递归实现DFS的伪代码和Python代码示例。该算法一般采用a堆栈为了跟踪访问的节点,因为最后看到的节点是下一个要访问的节点,其余的节点存储以便以后访问。
伪代码[1]
1 2 3 4 5 6 7 8 9 10对每个顶点u,定义u.visited为false。将根(第一个要访问的节点)推入S。当S不是空的时候:在S中弹出第一个元素,u。如果u.visited = false,那么:u.visited = true对于u的每个未访问的邻居w:当所有节点都被访问后,将w推入S。
没有递归的Python实现
1 2 3 4 5 6 7 8defdepth_first_search(图):参观了,堆栈=集(),[根]而堆栈:顶点=堆栈.流行()如果顶点不在参观了:参观了.添加(顶点)堆栈.扩展(图[顶点]-参观了)返回参观了
DFS还可以使用递归实现,这大大减少了代码行数。
使用递归的Python实现
1 2 3 4 5 6 7defdepth_first_search_recursive(图,开始,参观了=没有一个):如果参观了是没有一个:参观了=集()参观了.添加(开始)为下一个在图[开始]-参观了:depth_first_search_recursive(图,下一个,参观了)返回参观了
修改算法以跟踪边而不是顶点是很常见的,因为每条边都描述了每一端的节点。这在处理每个节点后试图重建遍历树时很有用。对于森林或一组树,该算法可以扩展为包含一个外部循环,该循环遍历所有树,以处理每个单独的节点。
实现DFS有三种不同的策略:预购,按次序的,后序.
预购DFS的工作原理是访问当前节点,然后依次向左移动,直到到达一个叶子节点,访问路径上的每个节点。一旦节点左边没有子节点,就会访问右边的子节点。这是最标准的DFS算法。
不是在遍历树时访问每个节点按次序的算法找到树中最左边的节点,访问该节点,然后访问该节点的父节点。然后它转到右边的子节点,找到树中最左边的下一个要访问的节点。
一个后序策略的工作原理是访问树中最左边的叶子,然后上到父节点,下到同一分支中最左边的第二个叶子,以此类推,直到父节点成为分支中最后一个被访问的节点。如果目标位于树的末端,这种算法优先处理叶子,然后处理根。
深度优先搜索的复杂性
深度优先搜索访问每个顶点一次,检查图中的每条边一次。因此,DFS的复杂度为 .这假设图被表示为邻接表.
DFS vs BFS
广度优先搜索比深度优先搜索的空间效率更低,因为BFS保留了整个边界的优先队列,而DFS在每一层维护了一些指针。
如果知道答案很可能在树的深处找到,那么DFS是比BFS更好的选择。当树的深度可以变化,或者需要一个单一的答案时(例如,树中的最短路径),可以使用BFS。如果要遍历整个树,DFS是一个更好的选择。
BFS总是返回一个最佳答案,但DFS不能保证这一点。
下面是一个示例,它比较了使用BFS和DFS(通过三种方法)时搜索图的顺序。[2]
广度优先搜索1 .单词expansion联想记忆
深度优先搜索
- 预定:1 2 4 5 3
- 顺序:4 2 5 1 3
- 订购后:4 5 2 3 1
应用程序
参考文献
- 堆,D。深度优先搜索(DFS).2002年12月16日,从http://www.cs.toronto.edu/~heap/270F02/node36.html
- Gupta, D。二叉树的BFS vs DFS.2016年7月20日,从http://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/