BFS和DFS

BFS

概述

1. 广度优先搜索（Breadth-First Search，简称 BFS）是一种遍历或搜索图或树数据结构的算法
2. 它从根节点开始，沿着树的宽度遍历节点（即先访问同一层级的所有节点，再访问下一层级的节点）
3. 在图中，BFS 从起始节点开始，探索所有邻居，然后依次遍历每个邻居的邻居，直到访问到目标节点或所有节点

特征

1. 层级遍历
   1. BFS 按照层级顺序访问节点，即先访问距离起点最近的节点，再访问次近的节点
2. 最短路径
   1. 在未加权图中，BFS 可以找到从起点到目标节点的最短路径

步骤

1. 初始化
   1. 创建一个队列，用于存储待访问的节点
   2. 将起始节点标记为已访问，并将其入队
2. 迭代
   1. 从队列中取出一个节点，将该节点的所有未访问的邻居节点标记为已访问，并将其入队
   2. 重复上述过程，直到队列为空或找到目标节点

示例无向图

1. 从节点 A 开始进行 BFS 遍历
2. 访问 A，将 A 的邻居 B 和 C 入队：Q = [B, C]
3. 访问 B，将 B 的邻居 D 和 E 入队：Q = [C, D, E]
4. 访问 C，将 C 的邻居 F 入队：Q = [D, E, F]
5. 访问 D：Q = [E, F]
6. 访问 E：Q = [F]
7. 访问 F：Q = []
8. 访问顺序为：A -> B -> C -> D -> E -> F

时间复杂度

1. O(V + E)，其中 V 是节点数量，E 是边数量。每个节点和每条边都会被访问一次

空间复杂度

1. O(V)，用于存储访问标记和队列

场景

1. 最短路径问题
   1. 在无权图中找到从起点到目标节点的最短路径
2. 连通性问题
   1. 检测图中所有节点是否连通，找到所有连通分量
3. 树的层次遍历
   1. 逐层遍历树的节点
4. 拓扑排序
   1. 在有向无环图中找到拓扑排序的一种方法
5. 迷宫求解
   1. 在迷宫或网格中找到从起点到终点的最短路径

示例代码

DFS

概述

1. 深度优先搜索（Depth-First Search，简称 DFS）是一种遍历或搜索图或树数据结构的算法
2. 它沿着树的深度遍历节点，尽可能深入树的分支
3. 在图中，DFS 从起始节点开始，沿着一个分支尽可能深入节点，直到到达叶子节点或没有未访问的邻居节点
   1. 然后回溯并探索其他分支

特征

1. 深度优先
   1. DFS 按照深度优先的策略访问节点，即尽可能深入每一个分支
2. 递归或栈实现
   1. DFS 可以使用递归或显式栈来实现

步骤

1. 初始化
   1. 创建一个栈（或使用递归调用栈）用于存储待访问的节点
   2. 将起始节点标记为已访问，并将其入栈
2. 迭代
   1. 从栈中取出一个节点，将该节点的所有未访问的邻居节点标记为已访问，并将其入栈
   2. 重复上述过程，直到栈为空或找到目标节点

示例无向图

1. 初始化栈：S = [A]
2. 访问 A，将 A 的邻居 B 和 C 入栈：S = [C, B]
3. 访问 B，将 B 的邻居 D 和 E 入栈：S = [C, E, D]
4. 访问 D：S = [C, E]
5. 访问 E：S = [C]
6. 访问 C，将 C 的邻居 F 入栈：S = [F]
7. 访问 F：S = []
8. 访问顺序为：A -> B -> D -> E -> C -> F

时间复杂度

1. O(V + E)，其中 V 是节点数量，E 是边数量。每个节点和每条边都会被访问一次

空间复杂度

1. O(V)，用于存储访问标记和递归栈或显式栈

场景

1. 路径查找
   1. 在图中找到从起点到目标节点的路径
2. 连通性问题
   1. 检测图中所有节点是否连通，找到所有连通分量
3. 拓扑排序
   1. 在有向无环图中找到拓扑排序的一种方法
4. 图的遍历
   1. 遍历图的所有节点，执行特定操作
5. 求解迷宫
   1. 在迷宫或网格中找到从起点到终点的路径
6. 检测环
   1. 检测图中是否存在环

示例代码

1. 栈实现

2. 递归实现