图的遍历 图的遍历是指从图中某一顶点出发，按照某种规则访问图中所有顶点，且每个顶点仅被访问一次的过程。遍历算法是图论中的基础工具，广泛应用于路径搜索、连通性分析等问题。下面从核心目标、基本方法到具体算法逐步展开说明。 1. 遍历的核心目标与挑战 目标 ：系统性地访问所有顶点，避免重复或遗漏。 关键约束 ：每个顶点只能被访问一次（避免无限循环，尤其存在回路时）。 挑战 ：图的结构不确定（可能有环、孤立顶点或不连通分支），需设计通用规则。 2. 遍历的两种基本策略 遍历通常基于两种策略，对应不同的访问顺序逻辑： 深度优先遍历（DFS） ：优先沿着路径深入访问，直到尽头再回溯。 广度优先遍历（BFS） ：优先访问当前顶点的所有邻接顶点，再逐层扩展。 3. 深度优先遍历的详细步骤 以顶点 \( v \) 为起点： 访问顶点 \( v \) ：标记 \( v \) 为“已访问”。 递归深入 ：从 \( v \) 的邻接顶点中选取一个未访问的顶点 \( u \)，对 \( u \) 执行DFS。 回溯 ：当 \( u \) 的所有邻接顶点均被访问后，退回 \( v \)，继续检查 \( v \) 的其他未访问邻接顶点。 终止条件 ：所有顶点均被访问，或所有连通分支遍历完毕。 示例 （假设无向图）： 若图有边 \( A-B, A-C, B-D \)： 从 \( A \) 开始，访问 \( A \) → 选择 \( B \) → 访问 \( B \) → 选择 \( D \) → 访问 \( D \) → 回溯到 \( B \) → 回溯到 \( A \) → 选择 \( C \) → 访问 \( C \)。 顺序：A, B, D, C。 关键特性 ： 使用栈（递归或显式栈）管理回溯过程。 适合检测环、拓扑排序等问题。 4. 广度优先遍历的详细步骤 以顶点 \( v \) 为起点： 访问顶点 \( v \) ：标记 \( v \) 为“已访问”，并将 \( v \) 加入队列。 层序扩展 ：从队列中取出顶点 \( u \)，依次访问 \( u \) 的所有未访问邻接顶点，并加入队列。 重复步骤2 ：直到队列为空。 示例 （同上图）： 从 \( A \) 开始，访问 \( A \) → 队列加入 \( B, C \) → 取出 \( B \)，访问 \( B \) 的未访问邻接点 \( D \) → 队列加入 \( D \) → 取出 \( C \)（无未访问邻接点）→ 取出 \( D \)。 顺序：A, B, C, D。 关键特性 ： 使用队列保证按层访问。 适合最短路径问题（无权图）。 5. 遍历的应用场景 连通性检测 ：通过遍历确认图是否连通（访问顶点数是否等于总顶点数）。 生成树/森林 ：遍历过程中经过的边构成生成树（DFS生成树或BFS生成树）。 组件分析 ：对不连通图多次调用遍历算法，可识别所有连通分支。 6. 算法实现注意事项 数据结构 ：需记录顶点状态（未访问/已访问），邻接表或邻接矩阵存储图。 复杂度 ：两种遍历的时间复杂度均为 \( O(|V| + |E|) \)，其中 \( |V| \) 为顶点数，\( |E| \) 为边数。 通过以上步骤，图的遍历将系统性地揭示图的局部与全局结构，为更复杂的图算法奠定基础。