DFS和BFS

• 数据结构：通常都使用队列（对于BFS）或者递归（对于DFS）来实现搜索过程。

• 访问标记：都需要标记已访问的节点，以避免重复访问或者形成无限循环。

• 搜索过程：都是从起始节点开始，逐步探索其邻接节点，并按照一定的顺序或规则搜索整个图或树结构。

关于DFS的模板已经在之前给出，BFS的模板如下：

先熟悉一下STL的queue使用方法

BFS算法：

通常用队列（先进先出，FIFO）实现

初始化队列Q；
Q = {起点s};
标记s为已访问；
while（Q非空）
{
    取Q队首元素u；
    u出队；
    if（u==目标状态）
    {
        ……
    }
    else
    {
        所有与u相邻且未被访问的点进入队列；
        标记u为已访问；
    }
}

以下来自gpt的回答：

BFS 的适用场景：

最短路径问题：当需要找到两点之间的最短路径时，BFS是首选。因为BFS按层级逐步扩展，第一次到达目标节点时的路径长度就是最短的。

层级遍历：需要按层级遍历或者搜索图或树的情况下，BFS非常适合。例如，查找最小步数到达目标状态的问题，或者按层级检查是否存在某种模式或结构。

状态空间搜索：对于状态空间较小且搜索层级不深的情况，BFS能够有效地探索所有可能状态，如在迷宫、棋盘游戏等中找到最短路径。

无权图的最短路径：在无权图中，BFS可以快速找到从起点到所有其他节点的最短路径。

DFS 的适用场景：

深度优先遍历：需要完整遍历整个图或树的情况下，DFS是一种自然选择。例如，生成树的所有可能路径，或者检查图中是否存在特定路径。

解决路径和循环问题：DFS在寻找一条路径是否存在的问题上很有效。当问题要求找到一个解决方案时，可以利用DFS递归地探索所有可能的路径。

拓扑排序：DFS可以用于拓扑排序算法中，通过递归地访问所有节点来实现。

状态空间较大：当状态空间较大且需要深度搜索时，DFS可能更适合，因为它使用递归或者显式栈的方式，不需要维护太多状态。

总结：

BFS适合解决最短路径问题、层级遍历和状态空间搜索问题，特别是需要找到最短路径或者最少步数的情况下。

DFS适合解决完整遍历问题、路径搜索和状态空间较大的深度搜索问题，特别是需要找到一条路径或者所有解决方案的情况下。DFS不一定能够找到最短路径，因为它不考虑距离和路径长度，但BFS则可以。