关于宽搜 BFS 广度优先搜索的那点事

以前一直知道深搜是一个递归栈, 广搜是队列, FIFO 先进先出 LILO 后进后出啥的. DFS 是以深度作为第一关键词, 即当碰到岔道口时总是先选择其中的一条岔路前进, 而不管其他岔路, 直到碰到死胡同时才返回岔道口并选择其他岔路. 接下来将介绍的广度优先搜索 (Breadth First Search, BFS) 则是以广度为第一关键词, 当碰到岔道口时, 总是先一次访问从该岔道口能直接到达的所有节结点, 然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点, 以此类推, 直到所有结点都被访问为止. 这就跟平静的水面中投入一颗小石子一样, 水花总是以石子落水处为中心, 并以同心圆的方式向外扩散至整个水面, 从这点来看 BFS 和 DFS 那种沿着一条线前进的思路是完全不同的.

广度优先搜索 BFS 一般由队列实现, 且总是按层次的顺序来进行遍历, 其基本写法如下(可作模板用):

void BFS(int s)
{
    queue<int> 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) 继续循环.

例 1: 给出一个 mxn 的矩阵, 矩阵中的元素为 0 或 1. 称位置 (x,y) 与其上下左右四个位置 (x,y+1),(x,y-1),(x+1,y),(x-1,y) 是相邻的. 如果矩阵中有若干个 1 是相邻的(不必两两相邻), 那么称这些 1 构成了一个 "块". 求给定的矩阵中 "块" 的个数.

[输入样例]

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

[解题思路]

求解的基本思想是: 枚举每一个位置的元素, 如果为 0, 则跳过; 如果为 1, 则使用 BFS 查询与该位置相邻的 4 个位置(前提是不出界), 判段它们是否为 1(如果某个相邻的位置为 1, 则同样去查询与该位置相邻的 4 个位置, 直到整个 "1" 块访问完毕). 而为了防止走回头路, 一般可以设置一个 bool 型数组 inq 来记录每个位置是否在 BFS 中已入过队.

对当前位置 (x,y) 来说, 由于与其相邻的四个位置分别为(x,y+1),(x,y-1),(x+1,y),(x-1,y), 那么不妨设置两个增量数组, 来表示四个方向.

int X[4] = {
	0,0,1,-1	
};
int Y[4] = {
	1,-1,0,0	
};

这样就可以使用 for 循环来枚举 4 个方向, 以确定与当前坐标 (nowX, nowY) 相邻的 4 个位置, 如下所示:

for(int i = 0;i<4;i++)
{
newX = nowX + X[i];
newY = nowY + Y[i];
}
#include <bits/stdc++.h>
#include <queue>
using namespace std;
const int maxn = 100;
struct node {
    int x,y; // 位置(x,y)
}Node;
int n,m; // 矩阵大小为 n*m
int matrix[maxn][maxn]; //01 矩阵
bool inq[maxn][maxn]; // 记录位置 (x,y) 是否已入过队
int X[4] = {0,0,1,-1}; // 增量数组
int Y[4] = {1,-1,0,0};
bool judge(int x,int y) // 判段坐标 (x,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<node>Q; // 定义队列
    Node.x = x, Node.y = y; // 当前结点的坐标为(x,y)
    Q.push(Node); // 将结点 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()
{
    freopen("1.txt","r",stdin); // 从文件读入
    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;
}

例 2

5 5

.....

.*.*.

.*S*.

.***.
...T*
2 2 4 3
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
struct node
{
    int x,y; // 位置(x,y)
    int step;//step 为从起点 S 到达该位置的最少步数(即层数)
}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<node> q; // 定义队列
    q.push(S); // 将起点 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++) // 循环 4 次, 得到 4 个相邻位置
        {
            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()
{
    freopen("2.txt","r",stdin);
    cin>>n>>m;
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<m;j++)
            cin>>maze[i][j];
    }
    cin>>S.x>>S.y>>T.x>>T.y;// 起点和终点的坐标
    S.step = 0; // 初始化的起点的层数为 0,S 到 T 的最少步数
    cout<<BFS()<<endl;
    return 0;
}

例 3

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x,y,z;
}Node;
int n,m,L,T;   // 矩阵为 n*m, 共有 L 层, T 为 1 的个数的下限
int pixel[1290][130][61];   // 三位 01 矩阵
bool inq [1290][130][61] = {false};
int X[6] = {0,0,0,0,1,-1};   // 增量矩阵
int Y[6] = {0,0,1,-1,0,0};
int Z[6] = {1,-1,0,0,0,0};
bool judge(int x,int y,int z)
{
    if(x>=n||x<0||y>=m||y<0||z>=L||z<0)
        return false;
    if(pixel[x][y][z] == 0 || inq[x][y][z] == true) return false;
    return true;
}
int BFS(int x,int y,int z)
{
    int tot = 0; // 计数当前块中 1 的个数
    queue<node> Q;   // 定义队列
    Node.x = x,Node.y = y,Node.z = z;
    Q.push(Node); // 将结点 Node 入队
    inq[x][y][z] = true; // 设置位置 (x,y,z) 已入过队
    while(!Q.empty())
    {
        node top = Q.front(); // 取出队首元素
        Q.pop();
        tot++;
        for(int i = 0;i<6;i++)
        {
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            int newZ = top.z + Z[i];
            if(judge(newX, newY,newZ))
            {
                Node.x = newX,Node.y=newY,Node.z = newZ;
                Q.push(Node);
                inq[newX][newY][newZ]= true;
            }
        }
    }
    if(tot>=T) return tot;
    else return 0;
}
int main()
{
    freopen("3.txt","r",stdin);
    cin>>n>>m>>L>>T;
    for(int z = 0;z<L;z++)
        for(int x = 0;x <n;x++)
            for(int y = 0;y<m;y++)
                cin>>pixel[x][y][z];
    int ans = 0;   // 记录卒中核心区 1 的个数总和
    for(int z =0;z<L;z++)
        for(int x = 0;x<n;x++)
            for(int y = 0;y<m;y++)
                if(pixel[x][y][z] == 1 && inq[x][y][z] == false)
                {
                    ans += BFS(x,y,z);
                }
    printf("%d\n",ans);
    return 0;
}

来源: http://www.bubuko.com/infodetail-3327295.html