自动驾驶小白说 🏎️4.2 DFS
type
status
slug
date
summary
tags
category
password
icon
彗星般的人生可以短暂，但绝不黯淡或沉沦。
— 纳兰容若
🏰代码及环境配置：请参考0.2 环境配置和代码运行 | 动手学运动规划!
深度优先搜索（Depth-First-Search，简称DFS）是一种基于图或搜索树的算法，从起始顶点开始选择某一路径深度试探查找目标顶点，当该路径上不存在目标顶点时，回溯到起始顶点继续选择另一条路径深度试探查找目标顶点，直到找到目标顶点或试探完所有顶点后回溯到起始顶点，完成搜索。
4.2.1 数据结构-栈
栈是一种后进先出(LIFO)的容器，如下图：
4.2.2 DFS算法的实现
由于DFS是以后进先出的方式遍历顶点，因此可以使用栈或者递归的方式来实现，以栈实现DFS为例，其算法步骤如下：
- 初始化：
- 创建一个栈
S，用于存储待访问的节点。 - 创建一个数组
visited，用于标记已访问过的节点。 - 将起始节点放入栈，并标记为已访问。
- 循环遍历：
- 当栈不为空时，执行以下操作：
- 从栈中弹出（或称为“出栈”）一个节点，记为
v，若节点v就是目标节点goal，则提前返回。 - 访问节点
v的所有未访问的邻接节点。 - 对于每个未访问的邻接节点，将其加入栈，并标记为已访问，同时记录当前节点
v为邻接节点的父节点。
- 回溯路径：
- 从目标节点开始，通过父节点向回追溯，直到起始节点，最终得到一条路径。
DFS的非递归实现（使用栈的数据结构）：
4.2.3 DFS算法的图解
以从下面的无权图中找到从节点
0 到节点3 的一条路径（注意：节点2 和节点3 之间不连通）为例，说明一下DFS算法的工作流程：
- 初始化一个空的栈和一个空的数组，其中栈用来存储未被访问过的节点，数组用来存储节点是否被访问过。
- 访问节点
0，并将它未被访问过的邻近节点（3，1，2）放入栈中，邻近节点（3，1，2）的父节点是0，其中放入栈中的顺序是自己定义的。
- 现在，节点
1在栈的顶部，因此访问节点1并从栈中取出节点1，然后将节点1所有未被访问过的邻近节点放入栈中（节点1没有邻近节点）。
- 节点
2在栈的顶部，因此访问节点2并从栈中取出节点2，然后将节点2所有未被访问过的邻近节点（4）放入栈中，节点4的父节点为2。
- 节点
4在栈的顶部，因此访问节点4并从栈中取出节点4，然后将节点4所有未被访问过的邻近节点放入栈中（节点4没有邻近节点）。
- 节点
3在栈的顶部，因此访问节点3并从栈中取出节点3，节点3就是目标节点，DFS算法遍历结束，并通过回溯父节点找到一条路径（0 —> 3）。
4.2.4 DFS算法优缺点
- 优点：
- DFS算法相对简单，容易理解和实现
- DFS算法特别适用于某些特定类型的问题，如寻找解的存在性、图的连通性检测等。
- 缺点：
- 在寻找最短路径的问题中，DFS不保证找到最优解，而是第一条符合要求的路径。
- 对于深度很大的图，DFS的递归深度也会很大，这可能会导致栈溢出等问题。
4.2.5 参考
Loading...
