图遍历

图遍历系统地访问图的顶点和边；广度优先搜索逐层探索，而深度优先搜索在回溯之前尽可能深入探索，它们共同构成了大多数图算法的基础。

Definition

图遍历是按系统顺序访问图的每个顶点（并检查每条边）的过程；广度优先搜索按与源的距离顺序访问顶点，而深度优先搜索在回溯之前跟踪每条路径直到其末端。

Scope

本主题涵盖两种基本的图搜索策略：广度优先搜索（BFS）和深度优先搜索（DFS），它们的基于队列和堆栈的实现，以及它们揭示的结构信息——可达性、连通分量、无权图中的最短路径、拓扑排序、环检测和强连通分量。它不包括加权最短路径和流问题，这些问题建立在遍历之上但单独处理。

Core questions

• BFS和DFS在访问顶点的顺序上有何不同，它们各自揭示了什么？
• BFS如何在无权图中计算最短路径？
• DFS如何实现拓扑排序、环检测和分量分解？
• 为什么这两种遍历的时间复杂度都与顶点数加边数呈线性关系？
• 如何使用已访问标记和前沿结构来避免重复访问顶点？

Key concepts

• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 已访问集合
• 队列和堆栈前沿
• 连通分量
• 拓扑排序
• 环检测
• 强连通分量

Key theories

广度优先搜索和无权最短路径

BFS使用队列按与源的距离非递减顺序访问顶点，因此它以线性时间计算从源到每个可达顶点的最小边数。

深度优先搜索和线性图算法

DFS凭借其发现时间和完成时间以及边分类，能够实现拓扑排序、环检测和查找强连通分量的线性时间算法，正如塔扬所系统化的那样。

Clinical relevance

遍历算法无处不在：BFS在无权网络中查找最短跳数，并支撑网络爬虫和点对点广播；DFS通过拓扑排序、死锁检测、迷宫和谜题求解以及社交和生物网络中的分量分析来驱动依赖解析和构建系统。

History

广度优先搜索可追溯到摩尔（Moore）1959年关于迷宫路由的工作以及相关的独立研究。深度优先搜索由罗伯特·塔扬（Robert Tarjan）于1972年奠定了严格的算法基础，他针对强连通分量和双连通性的线性时间算法证明了DFS是一种强大的通用工具。

Key figures

• Robert Tarjan
• Edward F. Moore
• John Hopcroft

Seminal works

• tarjan1972
• cormen2009

Frequently asked questions

我应该何时使用BFS而不是DFS？

当您需要以边数衡量的最短路径，或者希望按与源的距离顺序探索图时，请使用BFS。对于关于结构的问题——拓扑排序、环检测、连通或强连通分量——其中深入探索和回溯是自然的方式，请使用DFS。

为什么BFS和DFS都是线性时间？

每个顶点都被标记为已访问并处理一次，每条边都被检查恒定次数，因此总工作量与顶点数加上边数成比例，记作O(V + E)。