BFS & DFS

DFS和BFS的优缺点及应用场景

深度优先搜索的步骤分为:

1. 递归下去
2. 回溯上来。

DFS（Depth-First Search）是一种图遍历算法，用于在图形或树形数据结构中遍历所有节点。该算法从根节点开始，沿着某一分支一直遍历到底部，然后返回到上一级节点，继续遍历下一个分支，直到遍历完整个图。

DFS的优点包括：

1. 空间复杂度较低。DFS只需要保存当前路径上的节点，因此空间复杂度较低。如果图的规模非常大，DFS可能是更好的选择。
2. 可以找到一个解就返回。DFS不需要遍历整个图，一旦找到一个解就可以返回。因此，如果只需要找到一个解或者判断是否存在一个解，DFS可能比BFS更高效。
3. 可以处理边权重不同的图。DFS并不依赖于边权重，因此可以用于处理边权重不同的图。

DFS的缺点包括：

1. 可能无法找到最优解。由于DFS沿着某一分支一直遍历到底部，因此可能会错过更优的解。如果需要找到最优解，BFS可能是更好的选择。
2. 可能进入死循环。如果图中存在环路，DFS可能会陷入死循环，无法结束。
3. 时间复杂度较高。如果图的规模非常大，DFS可能会需要遍历大量的节点和边，因此时间复杂度可能较高。

总之，DFS适用于需要找到一个解或者处理边权重不同的图的问题，但可能无法找到最优解，可能进入死循环，时间复杂度也可能较高。

BFS（Breadth-First Search）是一种图遍历算法，用于在图形或树形数据结构中遍历所有节点。该算法从根节点开始，逐层遍历图中的节点，直到找到目标节点或遍历完整个图。

BFS的优点包括：

1. 可以找到从起点到终点的最短路径。由于BFS按照距离递增的顺序遍历节点，因此一旦找到目标节点，就可以保证是沿着最短路径到达的。
2. 可以找到所有从起点可达的节点。BFS遍历的顺序可以确保所有从起点可达的节点都会被遍历到，因此可以用于查找所有可达节点的问题。
3. 算法的实现相对简单。BFS的实现通常使用队列来保存待访问的节点，算法的复杂度为O(V+E)，其中V是节点数，E是边数。

BFS的缺点包括：

1. 空间复杂度高。BFS需要使用队列来保存待访问的节点，因此需要占用较多的内存空间。如果图的规模非常大，可能会导致内存不足。
2. 不适合处理边权重不同的图。BFS按照距离递增的顺序遍历节点，因此不适合处理边权重不同的图，如需要寻找最短路径的问题。
3. 时间复杂度较高。BFS的时间复杂度为O(V+E)，其中V是节点数，E是边数。如果图的规模非常大，可能会导致算法运行时间过长。

从依赖于内置调用栈的同步递归模型到具有链表和指针的异步模型

• 使用单链表树遍历算法
  • child 指向第一个child节点
  • sibling 指向第一个兄弟节点
  • return 指向父节点

保持对当前节点的引用，不断的遍历当前节点的第一个子节点，直到我们到达分支的末尾，然后通过return 这个引用来返回到父节点。