跳到主要内容

DFS

定义​

DFS（Depth First Search，深度优先搜索）是一种图的遍历算法，沿着树的深度遍历图的结点，尽可能深地搜索图的分支。

算法思想​

  1. 访问起始顶点 v，标记为已访问
  2. 选取 v 的一个未访问邻接顶点 w，递归对 w 进行 DFS
  3. 若 v 的所有邻接顶点都已访问，则回溯

实现​

通常使用递归或栈实现。

时间复杂度​

  • 邻接矩阵：O(V2)O(V^2)
  • 邻接表：O(V+E)O(V + E)

应用​

  • 拓扑排序
  • 连通分量检测
  • 迷宫求解
  • 回溯算法（全排列、子集等）