BFS

BFS—宽度优先搜索

💡 BFS是一个对连通图进行遍历的算法。它的思想是从一个被选定的点出发；然后从这个点依次向所有方向每散发，每次直走一步。（即其中一个方向走完一步之后换下一个方向继续走）；如果得不到目的解，那就返回事先定好的值，如果找到直接返回目的解。 与dfs不同的是，bfs不是运用的递归，而是运用队列和函数内循环构造的。

1. BFS算法思想：

💡 BFS：queue（队列） 时间复杂度：$O（2^N）$

BFS既宽度优先搜索，搜索方式为按层级搜索，先搜索第一层，再依次搜索下一层（既不管每一层元素有多少，都是按层级从上到下的顺序搜索），如果树或图的边权为 1 ，可作为最短路的方式搜索。BFS是通过队列实现的。

2. BFS算法实现方式：

• BFS通过队列实现，int g[N][N]，int d[N][N] //分别存储图和距离
• q[0] ={0, 0} 这里定义的是起点（题目要求从（0,0）起点开始）
• memset (d, -1, sizeof d) ，将d数组至为 -1，表示没有遍历（拓展）过
• int dx[4] = {-1, 0, 1, 0} , dy[4] = {0, 1, 0, -1};定义上下左右四个方向的扩展
• 如果点满足在图中的要求，则可以向不同的方向扩展
• 从上到下依次按层级遍历

3. BFS代码模板：

// BFS——套路模板
queue <-- 初始状态

while (queue 非空) 
{
	 t <-- 取出队头元素
   for (拓展 t) 
		{
       ver <-- 新节点
       if ( 该点未遍历 ) 
			 {
           在队尾插入 ver
       }
    }
}

// BFS——模板题 AcWing 846. 走迷宫
int bfs()
{
    int hh = 0, tt = 0;
    q[0] ={0, 0};
    
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    
    int dx[4] = {-1, 0, 1, 0} , dy[4] = {0, 1, 0, -1};//四个点的坐标分别为上，下，左，右
    
    while(hh <= tt)
    {
        auto t = q[hh ++ ];//取出队头
        
        for(int i = 0; i < 4; i ++)//让该点向不同的方向扩展
        {
            //表示能够扩展成功的方向
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[ ++ tt] = {x, y};
            }
        }
    }
    return d[n - 1][m - 1];
}