DFS and BFS

DFS

深度优先搜索，从名字上来看就是搜索深度更优先的搜索方式。它会“执着”地走到头，只有无路可走时，它才会后退（回溯）一步，寻找新的路径。若用 DFS 来遍历下面这颗树，那么下图节点上的数字便是 DFS 遍历的先后顺序，我们接下来就具体描述下该顺序： DFS 俗称暴力搜索，因为它遍历了所有可能情况，因此它的时间复杂度较高，能处理的数据规模较小。 但 DFS 每次搜索时只记录一条路径的信息，因此空间复杂度较低，为搜索深度。 代码模板

type dfs(type x, ... ) // 可以存在多个变量
{
    if( ... ) // 达成目标，找到答案
    {
        ... // 输出答案或判断最优解等等
        return;
    }
    if( ... ) // 达到搜索边界（即到边界了还没搜到，有时没有此步骤）
    {
        return;
    }
    for( ... ) // 遍历所有子节点
    {
        if( ... ) // 可以转移状态，一般用标志变量判断
        {
            ... // 修改标志变量，表明此节点不可转移
            dfs( ... ) // 搜索子节点，经常为x+1
            ... // 还原标志变量，表面此节点可转移
        }
    }
}

BFS

广度（宽度）优先搜索，侧重点就在搜索的广度。它会搜索完当前深度的所有节点，才会深入一层，搜索下一层的节点。若用 BFS 来遍历下面这颗树，那么下图节点上的数字便是 BFS 遍历的先后顺序，我们接下来就具体描述下该顺序： 可以发现一个性质就是，如果路径长度为 1 ，BFS 遍历到的节点深度就等于距起点的距离。因此可以通过 BFS 处理一些最短路问题。 BFS 也可以将所有情况遍历到，那么时间复杂度和 DFS 差不多。但 BFS 我们往往找到答案就会终止，并且可能更快找到答案，因此有时时间复杂度比 DFS 更好。

BFS 在每层遍历时需要保存该层所有节点，因此空间复杂度较高。

代码实现模板

bool vis[MAXN]; // 标记是否搜索过，有时也可直接用depth来判断
int depth[MAXN]; // 储存搜索深度，有时可能为二维数组或map
queue<type> que; // STL队列，不过数组模拟队列效率更高

type bfs(type start)
{
    que.push(start); // 起点入队
    depth[start] = 0; // 起点深度0
    vis[start] = true; // 标记起点
    while (!que.empty())
    {
        type now = que.front(); // 当前节点设置为队首
        que.pop(); // 弹出队首
        if ( ... ) // 如果达到目标条件
        {
            ans = depth[now]; // 储存答案
            return; // 搜索结束
        }
        for( ... ) // 遍历now节点的所有子节点，可用数组表示方向
        {
            type next = ... // 计算出子节点
            if (!vis[next] && ... ) // 如果子节点未搜索过，且范围符合题目条件
            {
                vis[next] = true; // 标记子节点
                depth[next] = depth[now] + 1; // 子节点深度+1
                que.push(next); // 子节点入队
                // 有时题目还需输出具体路径，可用一个数组储存每个节点的上一个节点，然后在此处对数组赋值。输出时，从结尾递归反向输出即可获得具体的路径。
            }
        }
    }
}

---

本文章使用limfx的vscode插件快速发布