【经验分享】数据结构——总结，图的深度优先遍历（DFS）和广度优先遍历（BFS）与二叉树遍历的比较

图是一种常见的数据格式，它的遍历主要分为两种： 深度优先遍历(DFS)：类似于二叉树的前序前序遍历 广度优先遍历(BFS)：类似于二叉树的层次遍历

深度优先遍历（DFS）

定义

深度优先遍历（DFS，Depth-First Search）是一种图遍历算法，它沿着图的深度方向进行搜索。DFS 从一个起始节点开始，优先访问未被访问的邻接节点，尽可能深地探索每个分支，直到所有可能的分支都被访问过，然后回溯到上一个节点继续探索。

与二叉树遍历的类比

• 前序遍历（Pre-order Traversal）：在二叉树中，前序遍历的顺序是“访问节点 → 访问左子树 → 访问右子树”。这个过程与 DFS 的过程非常相似，因为 DFS 也首先访问当前节点（或顶点），然后递归地访问所有未被访问的邻接节点。 类比解释: 在 DFS 中，节点被处理的顺序类似于前序遍历中的顺序，DFS 首先处理当前节点，然后递归地探索每个子节点。

广度优先遍历（BFS）

定义

广度优先遍历（BFS，Breadth-First Search）是一种图遍历算法，它沿着图的广度方向进行搜索。BFS 从一个起始节点开始，逐层访问所有邻接节点，然后继续访问这些邻接节点的邻接节点，直到图中的所有节点都被访问过。

与二叉树遍历的类比

• 层次遍历（Level-order Traversal）：在二叉树中，层次遍历按层访问所有节点。首先访问树的根节点，然后访问第二层节点，再访问第三层节点，以此类推。这个过程与 BFS 非常相似，因为 BFS 按层访问图的所有节点。 类比解释: 在 BFS 中，节点被访问的顺序类似于层次遍历中的顺序，BFS 逐层访问节点，每一层对应树的某一层。

例题

图的深度优先遍历类似于二叉树的( )。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历

题解

选A。图的深度优先遍历相当于 二叉树的前序遍历，因为它在访问节点时首先处理节点本身，然后递归地访问所有子节点。尽管 DFS 可以应用于任意图结构，而不仅限于树，但其遍历节点的顺序与二叉树的前序遍历最为接近。

总结

• 深度优先遍历（DFS） 与 前序遍历 类似，因为它们都优先访问当前节点，然后递归地访问所有未被访问的邻接节点。
• 广度优先遍历（BFS） 与 层次遍历 类似，因为它们都按层次访问图中的节点，逐层展开，直到遍历完整个图。