【算法与数据结构 03】什么是DFS和BFS？

这两周陷入了测试和作业的漩涡中，今天才有时间坐在电脑前码字了。好吧，我承认我是在找借口了QAQ

引入
介绍
- DFS
- BFS
应用
- DFS应用一：二叉树中的遍历
- DFS应用二：岛屿问题
- BFS应用一：二叉树的层序遍历
- BFS应用二：图的BFS
- BFS应用三：岛屿问题

引入

DFS(Depth First Search) 即深度优先搜索，而提到DFS就得说起BFS(Breadth First Search) 广度优先搜索了

在我的上一篇文章 二叉树的引入 当中，我有提到二叉树的前序、中序、后序遍历本质和DFS相同，而层序遍历本质和BFS相同，那么，DFS和BFS又是什么呢，怎么去实现它们呢~

来看看我在百科上看到的图，是和这次谈到的内容有关的哦~

自然界中的宽搜

介绍

DFS

假如去游玩一个市里面的景点，从景点0开始：

DFS的介绍

要去玩这些景点有很多种方式，那怎样才算是DFS呢~

这里先给出DFS的概念

深度优先搜索简单来说就是先深入探索，走到头再回退来寻找其他路径继续，以此反复的遍历方式

也就是说，它可以是这样去走的：

DFS的介绍

拿二叉树举例来说可以是这样走的（二叉树的前序遍历）：

二叉树的DFS

那如果不是二叉树呢，而是在一个图中呢，就比如一个二维数组中：

二维数组

又怎么走完这个图中的灰色部分呢？

首先依照遍历二维数组的方式，总可以找到第一个灰色部分，然后从这个灰色部分开始深入探索

因为是要走完所有的灰色部分，所以很显然要先探索与之相邻的四个方框（当然，不符合就直接return啦~）：

图的BFS

再然后像之前走完所有符合的路径就像下面这个样子了：

图的BFS

细心的读者可能会发现，因为是要探索与之相邻的四个方框，那么到下一相邻方框时岂不是要返回重新来过一遍，这里先将这个疑问放着，等介绍算法实现部分再来解释吧~

BFS

而BFS简单来说就是一层一层由内而外的遍历方式

那么，又怎么通过BFS的方式来走完上面的景点呢，它可以是这样走的：

BFS的介绍

对于二叉树来说差不多是这样走的（二叉树的层序遍历）：

二叉树的层序遍历

那如果是在一个二维数组中呢，与DFS又有什么不同呢？

它也是从一个方框依次向周围探索，与DFS区别不是很大，直接上图：

二维数组的BFS

相信到这里朋友们对于DFS和BFS是怎样走的应该了解了，那么接下来该说说它们的应用及算法实现了

应用

DFS应用一：二叉树中的遍历

DFS在二叉树中的遍历概括起来就是使用递归：

复制代码void dfs(TreeNode node) {
    if (node == null) {
        return;
    }
    dfs(node.left);
    dfs(node.right);
}

然后根据遍历父结点的顺序分为了前序、中序、后序遍历（这里不深入探讨了）

DFS应用二：岛屿问题

由 m*n 个小方块组成的网格上（每一个小方块都与周围四个相邻，可以参考上文），在这样的网格上进行搜索

空头说感觉不太好说，不如直接拿道题出来说说吧~

比如在这道题中：

463. 岛屿的周长

1表示陆地，0表示水域（目的是遍历完陆地的部分）：

岛屿的周长

在上文也提到从一个小方格要去探索周围四个方格，以此来走完所有陆地的部分

首先要注意的是边界的问题：

复制代码void dfs(int[][] grid, int r, int c){
    // 如果坐标不合法，直接返回
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
        return;
    }
}

另外要注意的就是上面留下的疑问了：遍历过的网格如何确定它遍历过没有，这样就不至于卡在死循环里

题目中是用数值来表示陆地和水域，那么可以改变遍历过的网格的数值（当然，这个值别是0、1就好），以此来判断它走没走过，是不是很巧妙 :D

最后实现起来大抵是这样：

复制代码void dfs(int[][] grid, int r, int c){
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
        return;
    }
    // 如果这个方格不是岛屿，也直接返回
    if (grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 2; // 标记遍历过的岛屿
    dfs(grid, r - 1, c); // 探索上边的方格
    dfs(grid, r + 1, c); // 下边的
    dfs(grid, r, c - 1); // 左边的
    dfs(grid, r, c + 1); // 右边的
}

除了上述两种应用较多外，还有其他的问题大抵上也都是用的回溯的思想

这里提到了回溯：从一条路往前走，能进则进，不能进则退回来，换一条路再试或者说自后向前，追溯曾经走过的路径

而想要实现回溯，可以利用栈的先入后出的特性，也可以采用递归的方式，而递归本身就是基于方法调用栈来实现的

而相对的，BFS的实现关键在于重放，也就是将遍历过的结点按之前的遍历顺序重新回顾，可以利用队列的先入先出的特性来实现。说那么多不如来看看下面的例子吧~

BFS应用一：二叉树的层序遍历

BFS在二叉树中的遍历使用队列：

复制代码void bfs(TreeNode node){
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(node);
    while (!queue.isEmpty()){
        int n = queue.size();
        for (int i = 0; i < n; i++) {
            TreeNode cur = queue.poll();
            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }
        }
    }
}

相比于DFS，BFS就显得比较繁琐了，这是因为递归隐含的使用了系统的栈，而我们就不需要自己维护一个数据结构了

除此之外，两者遍历结点的顺序也不同

BFS应用二：图的BFS

图的BFS

与层序遍历类似，同样需要使用队列，它的代码框架大概时这样的：

复制代码Queue<TreeNode> queue = new ArrayDeque<>();
while (!queue.isEmpty()){
    int n = queue.size();
    for (int i = 0; i < n; i++) {
        queue.poll();
        if () { // 若m结点没有访问过
            queue.add(m);
        }
    }
}

上面的岛屿问题也可以用BFS来实现，也与上面的图的BFS类似

BFS应用三：岛屿问题

图的BFS

同样的，0表示海洋，1表示陆地，从陆地依次向外遍历

BFS又是如何实现探索周围四个方块，这里可以用两个数组来间接实现：

复制代码void bfs(int[][] grid){
    //当前结点下标依次加上 dx[i], dy[i] 就可以得到新的下标
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
}

另外还需要队列来实现BFS，最后大概是这样子的：

复制代码void bfs(int[][] grid){
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    
    Queue<int[]> queue = new ArrayDeque<>();
    int m = grid.length, n = grid[0].length;
    // 将所有的陆地都入队。
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                queue.offer(new int[] {i, j});
            }
        }
    }
    
    // 然后从陆地开始一圈一圈的遍历
    int[] point = null;
    while (!queue.isEmpty()) {
        point = queue.poll();
        int x = point[0], y = point[1];
        // 取出队列的元素，将其四周的海洋入队。
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            // 边界的判断
            if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] != 0) {
                continue;
            }
            // 这里直接修改了原数组的值，以此来标记是否被访问
            grid[newX][newY] = grid[x][y] + 1; 
            queue.offer(new int[] {newX, newY});
        }
    }
}

感觉自己的输出效率蛮低的，可能还是不太会写博客吧，不过我会坚持下去的:D

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有