DFS-深度优先遍历

[yihan12]

深度优先遍历是一种图的遍历算法，它从图的起始顶点开始，沿着一条路径一直访问到最深的顶点，然后再回溯到上一个顶点，继续沿着另一条路径访问，直到遍历完所有顶点。

深度优先遍历通常使用递归或者栈来实现，具体步骤如下：

• 从起始顶点开始，访问该顶点，并标记为已访问；
• 递归访问该顶点的未访问邻接顶点，直到所有邻接顶点都被访问过；
• 如果当前顶点的所有邻接顶点都被访问过，回溯到上一个顶点，继续递归访问其未访问邻接顶点；
• 重复步骤2和步骤3，直到所有顶点都被访问过。

深度优先遍历的特点是能够沿着一条路径一直向下访问，直到最深的顶点，然后再回溯到上一个顶点，继续向下访问。它适合应用于寻找连通分量、拓扑排序等问题。