【算法笔记】数块数(BFS与DFS实现)

题目详情

问题背景

给出一个矩阵,矩阵中元素为0或1。称位置(x,y)与其上下左右四个位置(x,y+1)、(x+1,y)、(x-1,y)、(x,y-1)是相邻的。如果矩阵中有若干个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

题意理解

这是一个典型的“搜索”问题(注意区别算法概念中的“搜索”与“查找”)。如果我们把上述题目中的数字块,看成是图(其中的每个1都是图的一个顶点),那么数块数这个问题就可以转化为:求相互不连通的图的个数。显然,深度优先搜索(Depth First Search,简称DFS,在图的章节也叫深度优先遍历)或是广度优先搜索(Breadth First Search,简称BFS,在图的章节也叫广度优先遍历)算法都可以解决这个问题。

原书中提出这个问题,是为了展示广度优先搜索算法的工作方式。本文将提供深度优先和广度优先两种不同的方法的解。

hill

BFS实现

最终代码

#include <iostream>
#include <queue>

using namespace std;

const int MAX_N = 100;

struct Node {
    int x, y;
} node;

int rows, columns;
int matrix[MAX_N][MAX_N];
//定义bool型数组标记元素是否曾经入过队
bool enqueued[MAX_N][MAX_N] = {false};
//定义两个长度为4的数组作为增量序列(顺时针)
int X[4] = {0, 1, 0, -1};
int Y[4] = {1, 0, -1, 0};

//verify(int x, int y)函数用于判断某个位置是否应该被访问
bool verify(int x, int y) {
    if (x >= rows || x < 0 || y >= columns || y < 0) {
        return false;
    }
    if (matrix[x][y] == 0 || enqueued[x][y]) {
        return false;
    }
    return true;
}

void BFS(int x, int y) {
    queue<Node> q;
    node.x = x, node.y = y;
    cout << "(" << node.x << "," << node.y << ")";
    q.push(node);//起点元素入队
    enqueued[x][y] = true;//设置起点已入队
    Node front;
    int newX, newY;
    while (!q.empty()) {
        front = q.front();//取队首元素
        q.pop();//队首元素出队
        //分别检查与队首元素相邻的4个位置
        for (int i = 0; i < 4; ++i) {
            newX = front.x + X[i];
            newY = front.y + Y[i];
            //如果这个位置符合条件,则入队处理
            if (verify(newX, newY)) {
                node.x = newX, node.y = newY;
                q.push(node);
                enqueued[newX][newY] = true;
                cout << " -> " << "(" << node.x << "," << node.y << ")";
            }
        }
    }
    cout << endl;
}

int main() {
    //读入行数和列数
    cin >> rows >> columns;
    //读入矩阵
    for (int x = 0; x < rows; ++x) {
        for (int y = 0; y < columns; ++y) {
            cin >> matrix[x][y];
        }
    }
    int res = 0;
    //对每个块使用BFS
    for (int x = 0; x < rows; ++x) {
        for (int y = 0; y < columns; ++y) {
            if (matrix[x][y] == 1 && !enqueued[x][y]) {
                res++;
                BFS(x, y);
            }
        }
    }
    cout << res;
    return 0;
}

上述代码是用BFS实现的题解,有两点需要说明:

  • 其中34、51、55三行的作用是格式化输出每个块中1的访问顺序(两个坐标分别都从左上角的0开始),是为了让读者更容易理解BFS的过程,不是本题所要求的输出
  • 本文中的增量数组X[4]与Y[4]和原书中略有不同,主要是调整了顺序:原书中是先令x不动,y各增减1;再令y不动,x各增减1;本文中将这个序列改成了顺时针。这个改动对BFS的结果并不会造成很大的影响,两种方式输出的位置顺序略有不同,最终结果是一致的

输出结果

(0,1) -> (0,2) -> (0,3) -> (1,2)
(0,6)
(2,4) -> (3,4) -> (3,5) -> (4,4) -> (3,3)
(4,0) -> (4,1) -> (5,0) -> (4,2) -> (5,1) -> (5,2) -> (5,3)
4

过程解析

  1. 主函数中的双重for循环遇到的第一个1在(0,1)这个位置,这个1入队之后被设为已入队(enqueued[0][1]=1),块数加1
    1. 取(0,1)并出队,根据增量序列先访问(0,2),再顺时针访问(1,1)和(0,0)。其中(0,2)位置的数字为1且从未入队,因此该点入队;其他位置为0不做处理
    2. 取(0,2)并出队,与之前类似,(0,3)入队并标记
    3. 取(0,3)并出队,与之前类似,(1,2)入队并标记
  2. 之后双重for循环遇到了(0,6)处的1,这个1入队之后被设为已入队(enqueued[0][6]=1),块数加1;(0,6)周围4个位置都不需要处理,这一块结束
  3. 再接着双重for循环在(2,4)遇到了新块起始的1,这个1入队之后被设为已入队(enqueued[2][4]=1),块数加1
    1. 取(2,4)并出队,与之前类似,(3,4)入队并标记
    2. 取(3,4)并出队,与之前类似,按顺时针的顺序,(3,5)、(4,4)、(3,3)入队并标记
    3. 取(3,5)并出队
    4. 取(4,4)并出队
    5. 取(3,3)并出队
  4. 最后双重for循环遇到了最后一个1块起始点的坐标是(4,0),这个1入队之后被设为已入队(enqueued[4][0]=1),块数加1
    1. 取(4,0)并出队,与之前类似,(4,1)、(5,0)入队并标记
    2. 取(4,1)并出队,与之前类似,(4,2)、(5,1)入队并标记
    3. 取(5,0)并出队
    4. 取(4,2)并出队,与之前类似,(5,2)入队并标记
    5. 取(5,1)并出队
    6. 取(5,2)并出队,与之前类似,(5,3)入队并标记
    7. 取(5,3)并出队,所有的1搜索完成
lighthouse

DFS实现

最终代码

#include <iostream>

using namespace std;

const int MAX_N = 100;

int rows, columns;
int matrix[MAX_N][MAX_N];
//定义bool型数组标记元素是否已经被访问过
bool visited[MAX_N][MAX_N] = {false};
//定义两个长度为4的数组作为增量序列(顺时针)
int X[4] = {0, 1, 0, -1};
int Y[4] = {1, 0, -1, 0};

//verify(int x, int y)函数用于判断某个点是否应该被访问
bool verify(int x, int y) {
    if (x >= rows || x < 0 || y >= columns || y < 0) {
        return false;
    }
    if (matrix[x][y] == 0 || visited[x][y]) {
        return false;
    }
    return true;
}

void DFS(int x, int y, int layer) {
    visited[x][y] = true;
    layer == 1 ? cout << "(" << layer << "," << x << "," << y << ")" :
                 cout << " -> " << "(" << layer << "," << x << "," << y << ")";
    int newX, newY;
    for (int i = 0; i < 4; ++i) {
        newX = x + X[i];
        newY = y + Y[i];
        if (verify(newX, newY)) {
            DFS(newX, newY, layer + 1);
            visited[newX][newY] = true;
        }
    }
}

int main() {
    //读入行数和列数
    cin >> rows >> columns;
    //读入矩阵
    for (int x = 0; x < rows; ++x) {
        for (int y = 0; y < columns; ++y) {
            cin >> matrix[x][y];
        }
    }
    int res = 0;
    //对每个块使用DFS
    for (int x = 0; x < rows; ++x) {
        for (int y = 0; y < columns; ++y) {
            if (matrix[x][y] == 1 && !visited[x][y]) {
                res++;
                DFS(x, y, 1);
                cout << endl;
            }
        }
    }
    cout << res;
    return 0;
}

上述代码是用DFS实现的题解,有三点需要说明:

  • 其中28、29、57三行的作用是格式化输出每个块中1的访问顺序,不是本题所要求的输出
  • DFS相较于BFS函数中增加了一个layer变量(层数,也即深度,从1开始),主要是用于控制输出的坐标格式,同样不是本题所求
  • 与BFS类似,增量序列做了同样的调整

输出结果

(0,1) -> (0,2) -> (0,3) -> (1,2)
(0,6)
(2,4) -> (3,4) -> (3,5) -> (4,4) -> (3,3)
(4,0) -> (4,1) -> (4,2) -> (5,2) -> (5,3) -> (5,1) -> (5,0)
4

过程解析

  1. 主函数中的双重for循环遇到的第一个1在(0,1)这个位置,这个1被设为已访问(visited[0][1]=1),块数加1
    1. 从(0,1)出发可以访问到(0,2),同样进行标记
    2. 从(0,2)出发可以访问到(0,3),同样进行标记
    3. 从(0,3)出发访问不到任何1,退回(0,2)
    4. 从(0,2)出发可以访问到(1,2),同样进行标记
    5. 从(0,2)出发访问不到任何1,退回(0,1)
    6. 从(0,1)出发访问不到任何1,本块结束
  2. 之后双重for循环遇到了(0,6)处的1,这个1被设为已访问(visited[0][6]=1),块数加1;从(0,6)出发访问不到任何1,本块结束
  3. 再接着双重for循环在(2,4)遇到了新块起始的1,这个1被设为已访问(visited[2][4]=1),块数加1
    1. 从(2,4)出发可以访问到(3,4),同样进行标记
    2. 从(3,4)出发可以访问到(3,5),同样进行标记
    3. 从(3,5)出发访问不到任何1,退回(3,4)
    4. 从(3,4)出发可以访问到(4,4),同样进行标记
    5. 从(4,4)出发访问不到任何1,退回(3,4)
    6. 从(3,4)出发可以访问到(3,3),同样进行标记
    7. 从(4,4)出发访问不到任何1,退回(3,4)
    8. 从(3,4)出发访问不到任何1,退回(3,4)
    9. 从(3,4)出发访问不到任何1,退回(2,4)
    10. 从(2,4)出发访问不到任何1,本块结束
  4. 最后双重for循环遇到了最后一个1块起始点的坐标是(4,0),这个1被设为已访问(visited[4][0]=1),块数加1
    1. 从(4,0)出发可以访问到(4,1),同样进行标记
    2. 从(4,1)出发可以访问到(4,2),同样进行标记
    3. 从(4,2)出发可以访问到(5,2),同样进行标记
    4. 从(5,2)出发可以访问到(5,3),同样进行标记
    5. 从(5,3)出发访问不到任何1,退回(5,2)
    6. 从(5,2)出发可以访问到(5,1),同样进行标记
    7. 从(5,1)出发可以访问到(5,0),同样进行标记
    8. 从(5,0)出发访问不到任何1,退回(5,1)
    9. 从(5,1)出发访问不到任何1,退回(5,2)
    10. 从(5,2)出发访问不到任何1,退回(4,2)
    11. 从(4,2)出发访问不到任何1,退回(4,1)
    12. 从(4,1)出发访问不到任何1,退回(4,0)
    13. 从(4,0)出发访问不到任何1,本块结束

总结启发

  • 相比于BFS,DFS甚至不需要定义坐标的结构体,当然更不需要队列,代码看起来会短一些
  • DFS的递归边界实际上是if (verify(newX, newY)),这意味着并不是只有return;才可以结束递归。某一层递归中没有符合搜索条件的元素,不更进一层深入搜索的情况下这一层自然就结束了

发散思考

通过书上的代码,我们很明显地可以看到,BFS实际上是基于队列实现的。它要求每一个元素出队后,相邻元素入队,当队列中元素被全部取完的时候,就说明这个搜索过程结束了。

而DFS依赖的递归,实际上是一种程序栈。

那么进而我们产生了一种想法,如果把BFS实现中的对队列全部改成栈,它是不是就从BFS变成了DFS呢?

显然不是的。
home
  • 首先,递归用到的栈是程序栈,它和我们自己写的栈当然是两个不同的事物。递归代码改非递归在很多情境下都不是一件容易的事情,自然也不是自己写个栈就能完成的。
  • 其次,DFS与BFS实际上做的是同一件事情,它们的目的都是按照某种条件得到一个有序序列。但是这个有序,不是简单的按照深度或着按照广度,在大多数问题中这是一个二级排序。
    • 以广度优先为例,在某一层(某一轮确定了第一个元素之后)可能会有一系列满足条件的元素(是从同一个元素出发遍历得到的),接下来我们还要需要一个顺序条件才能确定最终的顺序,如果缺少这个条件,那么最后得到的序列就有可能是不唯一的。而在代码中用队列还是用栈,实际上决定的是第二级的顺序。
    • 在本题中,深度和广度的一级条件自不必说,二级条件实际上就表现成了那个增量序列。因此如果在本文BFS的基础上把队列改成栈,只是最终结果里的访问顺序从顺时针变成了逆时针(如果按照原书中的代码去修改,就表现得像是把增量序列的后三个分量倒过来)。这也是因为在BFS中,队列实际上只起到了一个容器的作用,无论这个容器是用队列还是栈,它只要能够把同一层的元素放在一起,就是满足条件的(因为本题没有规定第二级的顺序)。
  • 总的来说,把BFS中的队列改成栈,实际上仍旧是BFS。

  文章标题下的时间是文章的最新修改时间,鼠标悬停可以看到发布时间,请注意信息的有效性。
  版权声明:
    除非特殊说明,本站所有内容均为原创,采用 CC BY-NC-SA 4.0 许可协议进行共享 。
    需转载请注明原文标题:【算法笔记】数块数(BFS与DFS实现) 及链接:https://www.grobsr.com/some-counting-blocks/
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇