对比深搜与广搜

· · 个人记录

总结深搜和广搜的一些区别

深搜：一条路走到黑，不行就退一截再走到底

广搜：每条路都试探着走，一点一点往深处推进

拿一棵搜索形成的树来举例：

深搜遍历顺序： A B E F G K L M C D H I J

广搜遍历顺序： A B C D E F G H I J K L M

深搜：相当于树的先序遍历

广搜：相当于树的层次遍历

深搜：用的是栈空间，结点先进后出

广搜：用的是队列空间，结点先进先出

深搜：一个点可以搜到多次

广搜：一个点只能搜到一次，因为一般第一次搜到就是最优情况

深搜：应用更广，个人认为更好写

广搜：目前觉得在二维棋盘中求某点到某点的最短路径比较方便，因为第一个搜到的答案就是最短的路径

深搜模板：

int dfs(参数)
{
    判断当前结点是否合法，不合法直接返回
    判断当前结点是否符合结束条件，符合就返回答案
    标记当前结点为已搜
    for(int i=1; i<=生成结点数; i++){
        dfs(新结点的参数);
    }
    回溯，把当前节点标记为未搜
}

还有一种

int dfs(参数)
{
    判断当前结点是否符合结束条件，符合就返回答案
    标记当前结点为已搜
    for(int i=1; i<=生成结点数; i++){
        if(新生成的结点合法){
            dfs(新结点的参数);
        }
    }
    回溯，把当前节点标记为未搜
}

广搜模板：

//q是队列
int bfs(参数)
{
    初始化，把根节点入队
    while(!q.empty()){
        判断当前结点（q.front()）是否符合结束条件，符合就直接返回答案
        for(int i=1; i<=生成结点数; i++){
            if(新生成的结点合法 && 新生成的结点未搜过){
                q.push(新结点);
            }
        }
        标记当前结点为已搜
        q.pop();
    }
}