时间和空间复杂度

时间复杂度：

• O(V + E)
  • 构建邻接表时，每条边都会被访问一次；遍历过程中，每个顶点都会被访问，每条边也会被查看常数次。

空间复杂度：

• O(V + E)
  • 邻接表存储每条边，已访问数组和栈各自最多存放 V 个顶点。

总结：

• DFS 会先尽可能深入地探索，直到没有未访问的邻居时再回溯。
• 它的运行时间是线性的，也是许多图算法的基础。