点击刷新
前面介绍了深度优先搜索，可知DFS是以深度作为第一关键词的，即当碰到岔道口时总是先选择其中的一条岔路前进，而不管其他岔路，直到碰到死胡同时才返回岔道口并选择其他岔路。
接下来将介绍的广度优先搜索（Breadth FirstSearch，BFS)则是以广度为第一关键词，当碰到岔道口时，总是先依次访问从该岔道口能直接到达的所有结点，然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点，以此类推，直到所有结点都被访问为止。
这就跟平静的水面中投入一颗小石子一样，水花总是以石子落水处为中心，并以同心圆的方式向外扩散至整个水面，从这点来看
和DFS那种沿着一条线前进的思路是完全不同的。
广度优先搜索（Breadth First Search, BFS）遍历类似于树的按层次遍历的过程，则是以广度为第一关键词，当碰到岔道口时，总是先依次访问从该岔道口能直接到达的所有结点，
然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点，以此类推，直到所有结点都被访问为止。
广度优先搜索的整个算法过程很像一个队列，因此，广度优先搜索（Breadth First Search, BFS）一般由队列实现，且总是按层次进行遍历，
其基本写法如下（可用作模板用）：
void BFS(int s) { queue<int> q; q.push(s); while (!q.empty()) { 取出队首元素top 将队首元素出队 访问队首元素top 将top的下一层结点中未曾入队的结点全部入队，并设置为已入队 。 } }
下面是对该模板中每一个步骤的说明，请结合代码一起看：
①定义队列q，并将起点s入队。
②写一个 while循环，循环条件是队列q非空。
③在 while循环中，先取出队首元素top，然后访问它（访问可以是任何事情，例如将其输出）。访问完后将其出队。
④将top的下一层结点中所有未曾入队的结点入队，并标记它们的层号为now的层号加1，同时设置这些入队的结点已入过队
⑤返回②继续循环。
下面举一个例子，希望读者能从中学习BFS的思想是如何通过队列来实现的：
题目：
给出一个m* n的矩阵，矩阵中的元素为0或1。称位置(x, y)与其上下左右四个位置(x, y + 1)、(x, y - 1)、(x + 1, y)、(x - 1, y)是相邻的。
如果矩阵中有若干个1是相邻的（不必两两相邻），那么称这些1构成了一个“块”。求给定的矩阵中“块”的个数。
0111001
0010000
0000100
0001110
1110100
1111000
例如上面的6*7的矩阵，块的个数为4；
对这个问题，求解的基本思想是：
枚举每一个位置的元素，如果为0，则跳过；如果为1，则使用BFS查询与该位置相邻的4个位置（前提是不出界），判断它们是否为1
（如果某个相邻的位置为1，则同样去査询与该位置相邻的4个位置，直到整个“1”块访问完毕）。
而为了防止走回头路，一般可以设置一个bool型数组inq（即 In queue的简写）来记录每个位置是否在BFS中已入过队。
现在有一个小技巧是：对当前位置(x, y)来说，由于与其相邻的四个位置分别为(x, y + 1)、(x, y - 1)、(x + 1, y)、(x - 1, y)，
那么不妨设置下面两个增量数组，来表示四个方向（竖着看即为(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]; }
下列给出使用BFS搜索方法写出的代码：
#include<cstdio> #include<queue> using namespace std; const int maxn = 100; struct node { int x, y; }Node; int m, n; int matrix[maxn][maxn]; bool inq[maxn][maxn] = {false}; int X[4] = { 0,0,1,-1 }; int Y[4] = { 1,-1,0,0 }; bool judge(int x, int y) { if (x >= n || x < 0 || y >= m || y < 0) return false;//是否越界，越界返回个false if (matrix[x][y] == 0 || inq[x][y] == true) return false;//当前位置是否为0，是否已经入过队，返回false return true;//当前位置为1，且没有入过队 } void BFS(int x, int y) { queue<node> Q; Node.x = x; Node.y = y; Q.push(Node); inq[x][y] = true; while(!Q.empty()){ node top = Q.front(); Q.pop(); for (int i = 0; i < 4; i++) { int newX = top.x + X[i]; int newY = top.y + Y[i]; if (judge(newX, newY)) { Node.x = newX; Node.y = newY; Q.push(Node); inq[newX][newY] = true; } } } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &matrix[i][j]); } } int ans = 0; for (int x = 0; x < n; x++) { for (int y = 0; y < m; y++) { if (matrix[x][y] == 1 && inq[x][y] == false) { ans++; BFS(x, y); } } } printf("%d", ans); return 0; }
如果使用DFS搜索的话：
#include<cstdio> #include<queue> using namespace std; const int maxn = 100; struct node { int x, y; }Node; int m, n; int matrix[maxn][maxn]; bool inq[maxn][maxn] = { false }; int X[4] = { 0,0,1,-1 }; int Y[4] = { 1,-1,0,0 }; bool judge(int x, int y) { if (x >= n || x < 0 || y >= m || y < 0) return false; if (matrix[x][y] == 0 || inq[x][y] == true) return false; return true; } void DFS(int x, int y) { //当前点是块中点，先标记，然后横向遍历解答树所有子节点进行DFS inq[x][y] = true; for (int i = 0; i < 4; i++) {int newX = x + X[i]; int newY = y + Y[i]; if (judge(newX, newY)) DFS(newX, newY); } } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &matrix[i][j]); } } int ans = 0; for (int x = 0; x < n; x++) { for (int y = 0; y < m; y++) { if (matrix[x][y] == 1 && inq[x][y] == false) { ans++; DFS(x, y); } } } printf("%d", ans); return 0; }
相似的练习：
© 著作权归作者所有
发表评论
