C语言-广度优先搜索(BFS)

发布于 / 数据结构与算法 / Comments Off on C语言-广度优先搜索(BFS)

0x00、仍然从迷宫说起

昨天的文章(深度优先搜索),使用迷宫介绍了深度优先搜索,在介绍广度优先搜索前仍然以这个迷宫来介绍。

在深度优先搜索中,我们使用了朝向一个方向,全部遍历的方法,遍历了迷宫,走到了终点,在广度优先搜索中我们采取的措施有些不同:

用图来表示:

我们使用了层级,遍历迷宫

如果没有看不懂没关系,下面详细的讲解。

0x01、广度优先搜索的实现方式

我们使用一个队列来遍历迷宫:

我们先给岔路口编号,A,B,C和D,然后我们新建一个队列,放入第一层的节点,也就是{A}

下面,我们遍历队首元素A,首先让A出队,A的子节点有B和C,我们让B和C入队,队列状态为{B, C}

接着我们遍历队首元素B,B出队,B的子节点为D和5,入队。队列状态为{C, D, 5}

下面继续遍历队首元素C,C出队,C的子节点有终点和6,入队。队列状态为{D, 5, 终点, 6}

继续遍历队首的D,D出队,D的子节点2,3,4入队,队列状态为{5, 终点, 6, 2, 3, 4}

遍历队首元素5,5出队,发现5是死胡同了,停止。队列状态为{终点, 6, 2, 3, 4}

遍历队首元素"终点",发现是终点,停止BFS函数的执行,得出结果。

这种遍历的方式,我们称之为广度优先搜索,简称BFS(Breadth First Search)。

0x02、使用C语言实现广度优先搜索

广度优先搜索使用队列实现,基本写法如下:

void BFS(int s){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        取队首;
        访问队首;
        弹出队首;
        队首元素下一层级的元素全部入队;
    }
}

这里使用while循环实现,只要队列仍然有元素,就会不断遍历,直到找到终点。

0x03、举个例子

给出一个m*n的矩阵,矩阵的元素为0或1,定义 "相邻" 为上下左右四个位置。如果矩阵中有若干个 1 是相邻的(不必两两相邻),则这些 1 构成了一个"块",求给定矩阵中"块"的个数。单个 1 也算一块。

例如:

0 1 1 1 0 0 1        左边的6*7矩阵中

0 0 1 0 0 0 0        "块"的个数为4

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

在pat乙级中刷过这样类似的图案问题,我们可以定义一个表示"偏移量"的数组

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

这样,(X[1],Y[1]),(X[2],Y[2]),(X[3],Y[3]),(X[4],Y[4])就是四组偏移量。表示四个方向。

这个偏移量使用的时候可以使用for循环来枚举方向,确定坐标。

for(int i = 0; i < 4; i++){
    newX = nowX + X[i];
    newY = nowY + Y[i];
}

接着我们定义矩阵。矩阵的每个点应当存储输入的数值(data),并存储是否处理过该点(flag)。我们使用结构定义数组。

int n, m;    //矩阵大小为n*m
typedef struct{
    int data;
    bool flag;
} point;

point matrix[100][100];

为了方便,我们使用结构体定义坐标,并定义一个坐标类型的全局变量:Node

typedef struct{
    int x, y;
} node;
node Node;

我们可以使用一个裁定函数(judge)判断这个点是否应该入队。这个函数我们稍后实现。

我们先来实现BSF广度优先搜索函数。

void BFS(int x, int y){
    queue<node> Q;    //定义队列
    Node.x = x, Node.y = y;    //当前点的坐标
    Q.push(Node);    //将该点压入队列
    matrix[x][y].flag = true;    //将该点标记设置为 已入队
    while(!Q.empty()){
        node top = Q.front();    //取出队首
        Q.pop();                //队首出队
        for(int i = 0; i < 4; i++){    //循环4次,遍历四个方向
            int newX = top.x + X[i];
            int newY = top.y + Y[i];    //newX和newY在这四次循环中分别是4个方向上的点
            if(judge(newX, newY)){    //如果这个点需要访问
                Node.x = newX, Node.y = newY;    //让下一步处理的点变成这个需要等待处理的点
                Q.push(Node);    //将这个点压入队列,在队尾等待处理。
                matrix[newX][newY].flag = true;    //标记这个点已经入队。以后无需判断了
            }
        }
    }
}

这里面用到了judge函数,这个函数要求:

1,已入队的、曾经判断过的(flag=true)无需再次判断

2,该点为0的,肯定不是一个块的某个元素,无需判断

3,超过矩阵边界,会造成数组溢出,直接返回false,不可以判断

根据这三点,我们轻松的写出了judge函数

bool judge(int x, int y){
    /*数组越界情况*/
    if(x >= n || x < 0 || y >= m || y < 0)
        return false;
    /*当前位置为0,一定不是块元素,无需判断*/
    if(!matrix[x][y].data)
        return false;
    /*当前位置已经判断过了,或者已入队,无需重复判断*/
    if(matrix[x][y].flag)
        return false;
    /*以上都不满足,说明是一个从未判断过,并且数值为1的点,返回真*/
    return true;
}

OK,上面我们完成了广度优先搜索算法的全部步骤。下面我们来完成主函数:

int main(){
    cin >> n >> m;    //输入矩阵大小
    for(int x = 0; x < n; x++)
        for(int y = 0; y < m; y++){
            cin >> matrix[x][y].data;
            matrix[x][y].flag = false;
        }
    int result = 0;    //块数
    for(int x = 0; x < n; x++){
        for(int y = 0; y < m; y++){
            if(matrix[x][y].flag == false && matrix[x][y].data == 1){
                result++;
                BFS(x, y);
            }
        }
    }
    cout << "块数为:" << result << endl;
    return 0;
}

完整全部代码:

#include <iostream>
#include <queue>
using namespace std;

/*定义矩阵*/
int m, n;
typedef struct{
    int data;
    bool flag;
} point;
point matrix[100][100];

typedef struct{
    int x, y;
} node;
node Node;

/*偏移量相关*/
int X[] = {0, 0, 1, -1};
int Y[] = {1, -1, 0, 0};
bool judge(int x, int y){
    /*数组越界情况*/
    if(x >= n || x < 0 || y >= m || y < 0)
        return false;
    /*当前位置为0,一定不是块元素,无需判断*/
    if(!matrix[x][y].data)
        return false;
    /*当前位置已经判断过了,或者已入队,无需重复判断*/
    if(matrix[x][y].flag)
        return false;
    /*以上都不满足,说明是一个从未判断过,并且数值为1的点,返回真*/
    return true;
}

/*广度优先搜索函数*/
void BFS(int x, int y){
    queue<node> Q;    //定义队列
    Node.x = x, Node.y = y;    //当前点的坐标
    Q.push(Node);    //将该点压入队列
    matrix[x][y].flag = true;    //将该点标记设置为 已入队
    while(!Q.empty()){
        node top = Q.front();    //取出队首
        Q.pop();                //队首出队
        for(int i = 0; i < 4; i++){    //循环4次,遍历四个方向
            int newX = top.x + X[i];
            int newY = top.y + Y[i];    //newX和newY在这四次循环中分别是4个方向上的点
            if(judge(newX, newY)){    //如果这个点需要访问
                Node.x = newX, Node.y = newY;    //让下一步处理的点变成这个需要等待处理的点
                Q.push(Node);    //将这个点压入队列,在队尾等待处理。
                matrix[newX][newY].flag = true;    //标记这个点已经入队。以后无需判断了
            }
        }
    }
}

int main(){
    cin >> n >> m;    //输入矩阵大小
    for(int x = 0; x < n; x++)
        for(int y = 0; y < m; y++){
            cin >> matrix[x][y].data;
            matrix[x][y].flag = false;
        }
    int result = 0;    //块数
    for(int x = 0; x < n; x++){
        for(int y = 0; y < m; y++){
            if(matrix[x][y].flag == false && matrix[x][y].data == 1){
                result++;
                BFS(x, y);
            }
        }
    }
    cout << "块数为:" << result << endl;
    return 0;
}

运行结果:

转载原创文章请注明,转载自: 斐斐のBlog » C语言-广度优先搜索(BFS)
评论已关闭