DFS——深度优先搜索算法详解

深度优先搜索（DFS）是一种遍历树或图的算法。它会沿着一条路径尽可能往深处走，直到无法继续时再回溯。简单来说：DFS 会一直深入，走不通了，就回到上一个还有其他分支可走的位置。

如果你只记住一个核心概念，那就是：DFS 就是“先深入，再回溯”。

深度优先搜索做了什么

DFS 可以用于树，也可以用于一般图。它从某个节点出发，反复移动到一个尚未访问的相邻节点。当到达一个没有未访问相邻节点的节点时，它就回溯到前一个节点，并从那里继续。

回溯正是 DFS 最有代表性的行为。在递归实现中，调用栈会自动处理回溯。在迭代实现中，显式栈起到同样的作用。

DFS 并不会产生唯一固定的访问顺序。具体顺序取决于你按什么顺序检查相邻节点。

例如，如果某个节点的相邻节点是 $B$ 和 $C$ ，先访问 $B$ 得到的 DFS 顺序，可能和先访问 $C$ 不同。但这两种情况都仍然是 DFS，因为规则没有变：在探索同层其他分支之前，先尽可能往深处走。

假设图中有如下连接关系：

假设我们总是按从左到右的顺序检查相邻节点，并且从 $A$ 开始。

DFS 的过程如下：

因此，一个合法的 DFS 访问顺序是：

A, B, D, E, C, F

关键点在于，DFS 会先完成 $A \to B$ 这一侧的探索，再开始 $A \to C$ 这一侧。如果你改变相邻节点的顺序，访问顺序也可能随之改变。

DFS 总需要一种方式来记住：走到死路后应该返回哪里。这就是为什么栈会自然地出现在 DFS 中。

在递归版 DFS 中，每一次函数调用都会在搜索继续深入时等待；当开始回溯时，程序会按相反顺序返回。在迭代版 DFS 中，你把节点压入栈中，并在需要从最近一个尚未完成的点继续时将其弹出。

如果图使用邻接表存储，并且每个顶点在第一次访问时就被标记，那么 DFS 在图的可达部分上的运行时间是

O(V + E)

其中， $V$ 是顶点数， $E$ 是边数。

额外空间通常是

O(V)

因为已访问标记结构，以及递归栈或显式栈，都可能随着顶点数量增长。

在一般图中，如果忘记做已访问检查，DFS 可能会在一个环里无限循环。即使是在以无向图形式存储的树中，你也仍然需要避免立刻走回父节点，除非你的代码对这种情况做了明确处理。

DFS 可以找到一条路径，但在无权图中，它通常不能保证找到最短路径。如果目标是最短路径，并且所有边权都相同，那么 BFS 往往才是更合适的起点。

DFS 的访问顺序取决于相邻节点的顺序。如果这个顺序改变，遍历结果也可能改变。

当你想探索结构本身，而不只是优先考虑最近距离时，DFS 很有用。常见用途包括：

它之所以如此常见，主要是因为“先深入，再回溯”这种模式与许多递归问题的结构非常契合。

DFS 会先沿着一条分支向下走。BFS 则会先探索当前距离上的所有节点，再进入下一层距离。

如果你更关心完整探索或递归结构，DFS 往往很自然。如果你更关心无权图中的最短路径，BFS 通常是更稳妥的首选。

画一个有六个节点的小图，并固定相邻节点的访问顺序。手动运行一次 DFS，准确记录你什么时候前进、什么时候回溯。如果你在重新排列相邻节点后得到不同顺序，那不是 bug，而是 DFS 本来就会这样。

上传你的问题，几秒钟内获得经过验证的分步解答。