背景

Depth-First-Search(DFS)深度优先搜索与Breadth-First Search(BFS)广度优先搜索是树与图中最常用的算法。

DFS

适用于DFS场景：

  1. 在图中找到两个节点之间中最长路径
  2. 检测图中是否存在环
  3. 当一个树分支很多，使用BFS会导致内存不足或者占用太多，可以考虑使用DFS
  4. 需要在先访问子节点，再访问兄弟节点
  5. 通过DFS可以访问更多可能路径，可以用于解决迷宫与拼图问题

BFS

适用于BFS场景：

  1. 在图中找到两个节点之间的最短路径时
  2. 在断定目标节点在根节点或者起始节点附近（不需要深度搜索）
  3. 优先搜索靠近起始节点的节点
  4. 需要在先访问兄弟节点，再访问子节点