深度优先搜索

#深度优先搜索

• 什么是深度优先搜索
• 操作步骤
• 与广度优先搜索的对比
• 栈的应用

#什么是深度优先搜索

深度优先搜索（DFS）会沿着一条路径不断往下走，走到不能再走为止，然后折返，开始搜索下一条路径。

就像走迷宫：你沿着一条路一直走，走到死胡同就退回上一个岔路口，换一条路继续走。

        A
      / | \
     B  C  D
    /|  |  |\
   E F  H  I J
   |        |
   K   G    L

#操作步骤

以起点 A、终点 G 为例：

第1步: 从 A 出发，邻居 B、C、D 都可走 → 选最新加入的 B
       路径: A → B

第2步: 从 B 出发，邻居 E、F 可走 → 选最新的 E
       路径: A → B → E

第3步: 从 E 出发，邻居 K 可走 → 选 K
       路径: A → B → E → K

第4步: K 没有未访问的邻居了 → 折返到 E
       路径: A → B → E

第5步: E 没有其他邻居 → 折返到 B
       路径: A → B

第6步: 从 B 出发，走另一个邻居 F
       路径: A → B → F

  ...（继续折返和探索，最终到达 G）

搜索顺序: A → B → E → K → F → C → H → ... → G

#与广度优先搜索的对比

BFS 和 DFS 的操作步骤只有一点不同：选择候补顶点的基准不同。

#栈的应用

DFS 的候补顶点用栈（后入先出 LIFO）来管理：

候补栈:
  访问 A，邻居 B、C、D 入栈
  栈: [B, C, D] → 弹出 D（最新的）→ 不对，实际弹出顺序取决于入栈方式

  实际: A 的邻居入栈 → 栈顶是最先放入的还是最后放入的取决于实现
  DFS 的特点是：总是从最新加入的候补中选取下一个顶点

没有闭环的图叫作树。DFS 可以用于树的遍历（前序、中序、后序遍历）。

#小结

• DFS 沿着一条路径走到底，走不通再折返
• 用栈（LIFO）管理候补顶点，选择最新的候补
• 与 BFS 的唯一区别是选择候补的基准不同
• 不保证找到最短路径，但适合找所有路径、拓扑排序、检测环