图的深度优先搜索（DFS）

描述
深度优先搜索（DFS）是一种用于遍历或搜索图（或树）的算法。其核心思想是尽可能深地探索图的分支，直到当前分支的末端，然后回溯到上一个节点继续探索未访问的分支。DFS常用于解决路径查找、连通性检测、拓扑排序等问题。

步骤详解

1. 基本概念

   • 图由顶点（节点）和边（连接节点的线）组成。
   • DFS需要记录每个顶点是否被访问过（通常用一个布尔数组标记）。
   • 算法遵循“后进先出”的递归或栈结构，优先深入某一分支。

2. 算法流程
   步骤1：初始化

   • 创建一个访问标记数组visited[]，初始值为false（表示所有顶点未访问）。
   • 选择图的一个起点顶点。

   步骤2：从起点开始探索

   • 访问当前顶点（如输出其值），并将其标记为已访问。
   • 检查当前顶点的所有邻接顶点（即通过边直接相连的顶点）：
     • 若某个邻接顶点未被访问，则递归地对该邻接顶点执行DFS。
     • 若邻接顶点已被访问，则跳过。

   步骤3：回溯与终止

   • 当当前顶点的所有邻接顶点均被访问后，回溯到上一个顶点。
   • 算法在所有顶点均被访问时结束。

3. 示例（无向图）
   假设图如下（顶点0、1、2、3，边为0-1、0-2、1-3）：

     0
    / \
   1   2
   |
   3
   

   执行过程：

   • 从顶点0开始：标记0为已访问。
   • 检查0的邻接顶点（1和2），按顺序先访问1：标记1为已访问。
   • 检查1的邻接顶点（0和3），跳过已访问的0，访问3：标记3为已访问。
   • 3无未访问邻接顶点，回溯到1；1的邻接顶点已全部访问，回溯到0。
   • 0的另一个邻接顶点2未访问，访问2：标记2为已访问。
   • 2无未访问邻接顶点，回溯到0。算法结束。
     遍历顺序：0 → 1 → 3 → 2。

4. 代码实现（递归版）

   def dfs(graph, node, visited):
       visited[node] = True  # 标记当前节点已访问
       print(node)  # 处理节点（如输出）
       for neighbor in graph[node]:  # 遍历邻接节点
           if not visited[neighbor]:
               dfs(graph, neighbor, visited)  # 递归访问
   
   # 示例图的邻接表表示
   graph = {
       0: [1, 2],
       1: [0, 3],
       2: [0],
       3: [1]
   }
   visited = [False] * len(graph)
   dfs(graph, 0, visited)
   

5. 关键要点

   • 时间复杂度：O(V+E)（V为顶点数，E为边数）。
   • 空间复杂度：O(V)（递归栈或显式栈的空间）。
   • 若图不连通，需对每个未访问顶点调用DFS（避免遗漏）。
   • 非递归版本需用显式栈模拟递归过程（将节点入栈并循环处理）。

总结
DFS通过递归或栈实现“深度优先”的探索，适用于检测图的连通性、寻找路径、解决回溯问题等场景。理解其回溯机制和邻接顶点遍历顺序是掌握该算法的关键。