广度优先搜索(Breadth First Search， B F S {rm BFS} BFS ）则是以广度为第一关键词，当碰到岔道口时，总是先依次访问从该岔道口能直接到达的所有结点，然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点，以此类推，直到所有结点都被访问为止。这就跟平静的水面中投入一颗小石子一样，水花总是以石子落水处为中心，并以同心圆的方式向外扩散至整个水面（如下图所示)，从这点来看和 D F S {rm DFS} DFS 那种沿着一条线前进的思路是完全不同的。
为了讨论广度优先搜索是如何实现的，以下图的迷宫为例。同时也要注意，需要在广度优先搜索的过程中得出从起点到出口的最少步数（相邻两个能够直接到达的字母为一步)：
1）访问
A
{rm A}
A (第一层)，发现从
A
{rm A}
A 出发能到达
B
{rm B}
B 和
C
{rm C}
C (第二层)，因此接下来需要访问
B
{rm B}
B 和
C
{rm C}
C 。
2）访问
B
{rm B}
B (第二层)，发现从
B
{rm B}
B 出发能到达
D
{rm D}
D 和
E
{rm E}
E (第三层)，因此待第二层的结点全部访问完毕后需要访问
D
{rm D}
D 和
E
{rm E}
E 。
3）访问
C
{rm C}
C (第二层)，发现从
C
{rm C}
C 出发能到达
F
{rm F}
F 和
G
{rm G}
G (第三层)，因此待第二层的结点全部访问完毕后需要访问
F
{rm F}
F 和
G
{rm G}
G ，且它们排在
D
{rm D}
D 和
E
{rm E}
E 之后。
4）由于第二层访问完毕，因此需要访问第三层。访问
D
{rm D}
D (第三层)，发现从
D
{rm D}
D 出发能到达
H
、
I
、
J
{rm H、I、J}
H、I、J (第四层)，因此待第三层的结点全部访问完毕后需要访问
H
、
I
、
J
{rm H、I、J}
H、I、J 。
5）访问
E
{rm E}
E (第三层)，发现从
E
{rm E}
E 出发能到达
K
、
L
、
M
{rm K、L、M}
K、L、M (第四层)，因此待第三层的结点全部访问完毕后需要访问
K
、
L
、
M
{rm K、L、M}
K、L、M 。
6）访问
F
{rm F}
F (第三层)，发现
F
{rm F}
F 是死胡同，没有能直接到达的新结点，因此不予理睬。
7）访问
G
{rm G}
G (第三层)，发现
G
{rm G}
G 是出口，算法结束，至于那些第四层还没有访问的结点，就可以不用去访问了。
由上图迷宫可知， A {rm A} A 为第一层， B C {rm BC} BC 为第二层， D E F G {rm DEFG} DEFG 为第三层， H I J K L M {rm HIJKLM} HIJKLM 为第四层，并且这个层数就是从初始点 A {rm A} A 出发到达相应结点所需要的步数。由此可以知道，从起点 A {rm A} A 到出口 G {rm G} G 的最少步数为3（因为 G {rm G} G 在第三层)。
由上面的例子还可以发现，整个算法的过程很像一个队列，并且模拟的过程是这样的：
1）先在队列中放置初始点
A
{rm A}
A ，然后取出队首元素
A
{rm A}
A ，将
A
{rm A}
A 直接相连的
B
{rm B}
B 与
C
{rm C}
C 入队，此时队列内元素为
{
B
,
C
}
{rm {B,C }}
{B,C} 。
2）队首元素
B
{rm B}
B 出队，将
B
{rm B}
B 直接相连的
D
{rm D}
D 与
E
{rm E}
E 入队，此时队列内元素为
{
C
,
D
,
E
}
{rm {C,D,E }}
{C,D,E} 。
3）队首元素
C
{rm C}
C 出队（注意：队列的特性是先进先出，因此这里不是
D
{rm D}
D 出队)，将
C
{rm C}
C 直接相连的
F
{rm F}
F 与
G
{rm G}
G 入队，此时队列内元素为
{
D
,
E
,
F
,
G
}
{rm {D,E,F,G }}
{D,E,F,G} 。
4）队首元素
D
{rm D}
D 出队，将
D
{rm D}
D 直接相连的
H
、
I
、
J
{rm H、I、J}
H、I、J 入队，此时队列内元素为
{
E
,
F
,
G
,
H
,
I
,
J
}
{rm {E,F,G,H,I,J }}
{E,F,G,H,I,J} 。
5）队首元素
E
{rm E}
E 出队，将
E
{rm E}
E 直接相连的
K
、
L
、
M
{rm K、L、M}
K、L、M 入队，此时队列内元素为
{
F
,
G
,
H
,
I
,
J
,
K
,
L
,
M
}
{rm {F,G,H,I,J,K,L,M }}
{F,G,H,I,J,K,L,M}。
6）队首元素
F
{rm F}
F 出队，没有与
F
{rm F}
F 直接相连的新结点，此时队列内元素为
{
G
,
H
,
I
,
J
,
K
,
L
,
M
}
{rm {G,H,I,J,K,L,M }}
{G,H,I,J,K,L,M}。
7）队首元素
G
{rm G}
G 出队，找到出口，算法结束。
因此广度优先搜索（ B F S {rm BFS} BFS）一般由队列实现，且总是按层次的顺序进行遍历，其基本写法如下（可作模板用)：
void BFS(int s) {
queue q;
q.push(s);
while (!q.empty()) {
//取出队首元素top;
//访问队首元素top;
//将队首元素出队;
//将top的下一层结点中未曾入队的结点全部入队，并设置为已入队;
}
}
下面是对该模板中每一个步骤的说明，请结合代码一起看：
1）定义队列q，并将起点s入队。
2）写一个while循环，循环条件是队列q非空。
3）在while循环中，先取出队首元素 top，然后访问它（访问可以是任何事情，例如将其输出)。访问完后将其出队。
4）将top的下一层结点中所有未曾入队的结点入队，并标记它们的层号为now的层号加1，同时设置这些入队的结点已入过队。
5）返回步骤2继续循环。
下面举一个例子，希望读者能从中学习 B F S {rm BFS} BFS 的思想是如何通过队列来实现的：
给出一个 m × n {rm m times n} m×n 的矩阵，矩阵中的元素为0或1。称位置 ( x , y ) {rm (x,y)} (x,y) 与其上下左右四个位置 ( x , y + 1 ) 、 ( x , y − 1 ) 、 ( x + 1 , y ) 、 ( x − 1 , y ) {rm (x, y+1)、(x, y-1)、(x +1,y)、 (x-1,y)} (x,y+1)、(x,y−1)、(x+1,y)、(x−1,y) 是相邻的。如果矩阵中有若干个1是相邻的（不必两两相邻），那么称这些1构成了一个“块”。求给定的矩阵中“块”的个数。
0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0
例如上面的 6 × 7 {rm 6 times 7} 6×7 的矩阵中，“块”的个数为4。
对这个问题，求解的基本思想是：枚举每一个位置的元素，如果为0，则跳过；如果为1，则使用 B F S {rm BFS} BFS 查询与该位置相邻的4个位置(前提是不出界)，判断它们是否为1(如果某个相邻的位置为1，则同样去查询与该位置相邻的4个位置，直到整个“1”块访问完毕)。而为了防止走回头路，一般可以设置一个bool型数组inq（即in queue的简写）来记录每个位置是否在 B F S {rm BFS} BFS 中已入过队。
一个小技巧是：对当前位置 ( x , y ) {rm (x,y)} (x,y) 来说，由于与其相邻的四个位置分别为 ( x , y + 1 ) 、 ( x , y − 1 ) 、 ( x + 1 , y ) 、 ( x − 1 , y ) {rm (x, y+1)、(x, y-1)、(x +1,y)、 (x-1,y)} (x,y+1)、(x,y−1)、(x+1,y)、(x−1,y) ，那么不妨设置下面两个增量数组，来表示四个方向（竖着看即为 ( 0 , 1 ) 、 ( 0 , − 1 ) 、 ( 1 , 0 ) 、 ( − 1 , 0 ) {rm (0,1)、(0,-1)、(1, 0)、(-1,0) } (0,1)、(0,−1)、(1,0)、(−1,0)）。
int X[] = {0, 0, 1, -1};
int Y[] = {1, -1, 0, 0};
这样就可以使用for循环来枚举4个方向，以确定与当前坐标(nowX,nowY)相邻的4个位置，如下所示：
for (int i = 0; i < 4; i++) {
newX = nowX + X[i];
newY = nowY + Y[i];
}
下面给出本例的代码，希望读者能仔细理解代码中 B F S {rm BFS} BFS 的写法：
#include#include using namespace std; const int maxn = 100; //位置(x,y) struct Node { int x; int y; }; int n, m; //矩阵大小为n*m int matrix[maxn][maxn]; //01矩阵 bool inq[maxn][maxn] = {false}; //记录位置(x,y)是否已经入过队 int X[4] = {0, 0, 1, -1}; //增量数组 int Y[4] = {1, -1, 0, 0}; //判断坐标(x,y)是否需要访问 bool judge(int x, int y) { //越界返回false if (x >= n || x < 0 || y >= m || y < 0) return false; //当前位置为0，或(x,y)已经入过队，返回false if (matrix[x][y] == 0 || inq[x][y] == true) return false; //以上都不满足，返回true return true; } //BFS函数访问位置(x,y)所在的块，将该块中所有“1”的inq都设置为true void BFS(int x, int y) { queue Q; //定义队列 Node node; //当前结点的坐标为(x,y) node.x = x; node.y = y; Q.push(node); inq[x][y] = true; //设置(x,y)已入过队 while (!Q.empty()) { Node top = Q.front(); //取出队首元素 Q.pop(); //队首元素出队 for (int i = 0; i < 4; i++) { //循环4次，得到4个相邻位置 int newX = top.x + X[i]; int newY = top.y + Y[i]; if (judge(newX, newY)) { //如果新位置(newX,newY)需要访问 //设置node的坐标为(newX,newY) node.x = newX; node.y = newY; Q.push(node); //node入队 inq[newX][newY] = true; //位置(newX,newY)已经入过队 } } } } int main() { cin >> n >> m; for (int x = 0; x < n; x++) for (int y = 0; y < m; y++) cin >> matrix[x][y]; //读入01矩阵 int ans = 0; //存放块数 //枚举每一个位置 for (int x = 0; x < n; x++) for (int y = 0; y < m; y++) //如果元素为1，且未入过队 if (matrix[x][y] == 1 && inq[x][y] == false) { ans++; //块数加1 BFS(x, y); //访问整个块，将该块中所有“1”的inq都设置为true } cout << ans << endl; return 0; }
输入数据：
6 7 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0
输出结果：
4例二
接下来再看一个类似的例子。
给定一个n*m大小的迷宫，其中*代表不可通过的墙壁，而. 代表平地，S表示起点，T代表终点。移动过程中，如果当前位置是 ( x , y ) {rm (x,y)} (x,y) (下标从0开始)，且每次只能前往上下左右 ( x , y + 1 ) 、 ( x , y − 1 ) 、 ( x − 1 , y ) 、 ( x + 1 , y ) {rm (x,y+1)、(x,y-1)、(x-1,y)、(x+1,y)} (x,y+1)、(x,y−1)、(x−1,y)、(x+1,y) 四个位置的平地，求从起点S到达终点T的最少步数。
. . . . . . * . * . . * S * . . * * * . . . . T *
在上面的样例中，S的坐标为(2,2)，T的坐标为(4,3)。
在本题中，由于求的是最少步数，而 B F S {rm BFS} BFS 是通过层次的顺序来遍历的，因此可以从起点S开始计数遍历的层数，那么在到达终点T时的层数就是需要求解的起点S到达终点T的最少步数。
于是可以写出下面的代码：
#include#include "queue" using namespace std; const int maxn = 100; struct Node { int x, y; //位置(x,y) int step; //step为从起点S到达该位置的最少步数(即层数) }; Node S, T, node; //S为起点，T为终点，node为临时结点 int n, m; //n为行，m为列 char maze[maxn][maxn]; //迷宫信息 bool inq[maxn][maxn] = {false}; //记录位置(x,y)是否已入过队 int X[4] = {0, 0, 1, -1}; //增量数组 int Y[4] = {1, -1, 0, 0}; //检测位置(x,y)是否有效 bool test(int x, int y) { //超过边界 if (x >= n || x < 0 || y >= m || y < 0) return false; //墙壁* if (maze[x][y] == '*') return false; //已经入过队 if (inq[x][y] == true) return false; return true; //有效位置 } int BFS() { queue q; q.push(S); //起点S入队 inq[S.x][S.y] = true; //起点S已入队 while (!q.empty()) { Node top = q.front(); //取队首元素 q.pop(); //队首元素出队 if (top.x == T.x && top.y == T.y) return top.step; //终点，直接返回最少步数 for (int i = 0; i < 4; i++) { int newX = top.x + X[i]; int newY = top.y + Y[i]; if (test(newX, newY)) { //位置(newX,newY)有效 node.x = newX; node.y = newY; node.step = top.step + 1; //node层数为top的层数加1 q.push(node); //node入队 inq[newX][newY] = true; //设置位置(newX,newY)已入队 } } } return -1; //无法到达终点T时返回-1 } int main() { cin >> n >> m; for (int x = 0; x < n; x++) { getchar();//过滤掉每行后面的换行符 for (int y = 0; y < m; y++) cin >> maze[x][y]; } cin >> S.x >> S.y >> T.x >> T.y; //起点和终点的坐标 S.step = 0; //初始化起点的层数为0，即S到S的最少步数为0 cout << BFS() << endl; return 0; }
输入数据：
5 5 . . . . . . * . * . . * S * . . * * * . . . . T * 2 2 4 3
输出数据：
11
