宽度优先搜索（BFS，Breadth-First Search）也是搜索的手段之一，与深度优先搜索类似，从某个状态出发搜索所有可以到达的状态。
与深度优先搜索的不同之处在于搜索的顺序，宽度优先搜索总是先搜索距离初始状态最近的状态。也就是说，它是按照开始状态→只需一次转移就能到达的所有状态→只需2次就可以到达的所有状态→…按照这样的顺序进行搜索。对于同一个状态，宽度优先搜索只经过一次，因此时间复杂度为O（状态数×转移的方式）。
深度优先搜索利用了栈进行计算，而宽度优先搜索则利用了队列进行计算。搜索时首先将状态添加进队列里，此后从队列的最前端不断取出状态，把从该状态可以转移到的状态尚未访问过的部分加入到队列中，如此往复，直至队列被取空或找到了问题的解。通过观察这个队列，我们就可以知道所有的状态都是按照距初始状态由近及远的顺序遍历的。
例题：
迷宫的最短路径
给定一个大小为N×M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四个的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。（N,M≤100）（'#', '.' , 'S', 'G'分别表示墙壁、通道、起点和终点）
输入：
10 10
#S######.#......#..#.#.##.##.#.#........##.##.####....#....#.#######.#....#......####.###.....#...G#
输出：
22
代码：
#include#includeusing namespace std;const int INF = 100000000, maxn = 105;typedef pair P;//可以使用结构体char maze[maxn][maxn];int n, m, sx, sy, gx, gy,d[maxn][maxn];//到各个位置的最短距离的数组int dx[4] = { 1,0,-1,0 }, dy[4]= { 0,1,0,-1 };//4个方向移动的向量int bfs()//求从(sx,sy)到(gx,gy)的最短距离，若无法到达则是INF{queueque; for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)d[i][j] = INF;//所有的位置都初始化为INFque.push(P(sx, sy));//将起点加入队列中d[sx][sy] = 0;//并把这一地点的距离设置为0while (que.size())//不断循环直到队列的长度为0{P p = que.front();// 从队列的最前段取出元素que.pop();//取出后从队列中删除该元素if (p.first == gx&&p.second == gy)break;for (int i = 0; i < 4; i++)//四个方向的循环{int nx = p.first + dx[i],ny = p.second + dy[i];//移动后的位置标记为(nx,ny)if (0 > n >> m;sx = 0, sy = 1, gx = 9, gy = 8;//起点和终点坐标for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> maze[i][j];cout