BFS

BFS介绍

BFS，即宽度优先搜索，经常用于图上遍历等。相比于dfs,bfs是横向的搜索，是一层一层找的。

BFS通过队列进行依次处理，对于每个结点的子节点，将它通过排队的形式排在这一层的后面而非直接遍历，对于一颗BFS树，它的BFS序便是一层一层的向下拓展。

同时BFS由于是层层遍历，先访问到的一定是距离初始点最短的。

BFS模板

int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//四个方向上x,y轴分别的变化量
int vis[N][N];//该点是否被访问过
struct node{//分别存储x轴坐标值,y轴坐标值，起始点到当前点的最小步数
    int x,y,step;
};
int bfs(int sx,int sy,int tx,int ty){//x,y表示当前位置坐标，tx,ty表示目标位置坐标，该样例表示遍历图上每一个点
	queue<node>q;
    q.push({sx,sy,0});//加入初始点，即BFS树的根节点
    while(q.size()){
        node temp=q.front();//取出队列中的第一个元素并向下拓展，排在该层的所有结点的后面
        q.pop();
        int x=temp.x,y=temp.y,step=temp.step;
        if(x==tx&&y==ty)return step;//到达目的地直接返回即可
        if(vis[x][y])continue;
        vis[x][y]=1;
        for(int i=0;i<4;++i){
            int dx=x+d[i][0],dy=y+d[i][1];//原先的x轴方向的值再加上变化量就是现在的x值
            if(dx<0||dx>=n||dy<0||dy>=m)continue;//超出边界就不过去了
            q.push({dx,dy,step+1});
        }
    }
    return -1;
}

DFS与BFS的对比

搜索方向：dfs是纵向搜索，它能更好的体现一条数链上的传递关系，如父子关系，总价值等。bfs是横向搜索，它能保证每个点到起始点都是其层数，即都是最短路径，同时也能很容易获取某个结点位于哪一层。

处理的对象：dfs可以对于每个物品或每一步考虑不同的情况来进行遍历。bfs大部分都是处理树上问题以及图论部分。dfs在处理树上问题以及图论部分时需要考虑是否存在爆栈情况，在时间上bfs往往更优。

总而言之，dfs与bfs各有各自独特的应用场景，可以根据相应的情况选择合适的搜索方式。