BFS和DFS是什么

BFS (宽度优先搜索) 和 DFS (深度优先搜索) 都是图或树遍历算法的基本策略。

1. **BFS**（广度优先搜索）：它从起点开始，首先访问所有距离起点最近的节点，然后逐层地向外扩展，直到找到目标节点。常用于求最短路径问题，如迷宫问题、网络中寻找两个节点间的最短路径等。BFS通常需要维护一个队列数据结构来存储待访问的节点。

2. **DFS**（深度优先搜索）：它从起点开始，尽可能深地探索分支，即沿着一条路走到尽头再回溯。有三种常见的实现方式：前向搜索（先访问子节点，再返回）、后向搜索（先访问父节点，再返回）和迭代加深搜索（不断加深搜索深度）。DFS常用于查找连通分量、拓扑排序以及解决一些游戏状态遍历问题。