BFS和DFS

BFS和DFS

最近开始在刷图论和数的题，其中BFS和DFS算是比较基础的一个搜索“方法”了，于是特地去网上搜了一下，重新温习了以前学数据结构中学的这几个方法。

DFS

DFS(Depth First Search) :深度优先搜索

介绍

DFS，如其名，就是优先进行深度方面的搜索，先对一条路探索到底，然后回溯之后继续对另一条路探索到底，我愿将其称作不撞南墙不回头。

用法

DFS广泛的运用于图和树的搜索中，其中在树种的应用为前、中、后序遍历，这个在我的一篇文章中讲过，wy的leetcode刷题记录_Day30_二叉树起点！，其中代码实现也在里面；而对于图的应用可以用一个小例题来概括：岛屿问题：463. 岛屿的周长
1表示陆地，0表示水域（目的是遍历完陆地的部分）。
首先我们要注意边界的问题，也就是dfs的出口：

void dfs(int[][] grid, int r, int c){
   
    // 如果坐标不合法，直接返回
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
   
        return;
    }
}
1
2
3
4
5
6
7
8

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

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

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15