4.2 DFS

4.2.1 数据结构-栈

4.2.2 DFS算法的实现

1. 初始化：
• 创建一个栈S，用于存储待访问的节点。
• 创建一个数组visited，用于标记已访问过的节点。
• 将起始节点放入栈，并标记为已访问。

2. 循环遍历：
• 当栈不为空时，执行以下操作：
• 从栈中弹出（或称为“出栈”）一个节点，记为v ，若节点v 就是目标节点goal ，则提前返回。
• 访问节点v的所有未访问的邻接节点。
• 对于每个未访问的邻接节点，将其加入栈，并标记为已访问，同时记录当前节点v为邻接节点的父节点。

3. 回溯路径：
• 从目标节点开始，通过父节点向回追溯，直到起始节点，最终得到一条路径。

4.2.3 DFS算法的图解

1. 初始化一个空的栈和一个空的数组，其中栈用来存储未被访问过的节点，数组用来存储节点是否被访问过。

2. 访问节点0 ，并将它未被访问过的邻近节点（3，1，2）放入栈中，邻近节点（3，1，2）的父节点是0，其中放入栈中的顺序是自己定义的。

3. 现在，节点1 在栈的顶部，因此访问节点1 并从栈中取出节点1 ，然后将节点1 所有未被访问过的邻近节点放入栈中（节点1 没有邻近节点）。

4. 节点2在栈的顶部，因此访问节点2并从栈中取出节点2，然后将节点2所有未被访问过的邻近节点（4）放入栈中，节点4的父节点为2 。

5. 节点4在栈的顶部，因此访问节点4并从栈中取出节点4，然后将节点4所有未被访问过的邻近节点放入栈中（节点4没有邻近节点）。

6. 节点3在栈的顶部，因此访问节点3并从栈中取出节点3，节点3就是目标节点，DFS算法遍历结束，并通过回溯父节点找到一条路径（0 —> 3）。

4.2.4 DFS算法优缺点

• 优点：
• DFS算法相对简单，容易理解和实现
• DFS算法特别适用于某些特定类型的问题，如寻找解的存在性、图的连通性检测等。

• 缺点：
• 在寻找最短路径的问题中，DFS不保证找到最优解，而是第一条符合要求的路径。
• 对于深度很大的图，DFS的递归深度也会很大，这可能会导致栈溢出等问题。

4.2.5 参考