视频字幕
深度优先搜索是一种重要的图遍历算法。它的核心思想是从起始节点开始，尽可能深地探索图的分支。当遇到死路时，算法会回溯到上一个节点，继续探索其他未访问的分支。
让我们通过一个具体例子来演示深度优先搜索的执行过程。从节点0开始，我们首先访问它，然后选择邻居节点1继续深入。接着访问节点2，当无法继续深入时，回溯到节点1，再探索其他邻居节点3和4。
在C++中实现深度优先搜索需要几个关键组件。首先使用邻接表来表示图结构，然后定义一个递归函数来执行遍历。访问标记数组用来避免重复访问节点，而递归调用栈天然地支持了回溯机制。
这是一个完整的C++深度优先搜索实现。代码包含了图的构建、DFS递归函数和主函数调用。时间复杂度为O(V+E)，其中V是顶点数，E是边数。空间复杂度为O(V)，主要用于存储访问标记和递归调用栈。
总结一下深度优先搜索的要点：DFS是一种重要的图遍历算法，通过递归方式深入探索图的分支。在C++中使用邻接表表示图，配合访问标记和递归函数实现。算法时间复杂度为O(V+E)，广泛应用于各种图算法问题的解决。