深度优先算法

发表于 | 分类于 | |
字数统计: 649 | 阅读时长 ≈ 3

深度优先搜索

在之前的博客里面我们已经介绍了深度优先算法。实际上深度优先搜索一般可以用递归或者栈来实现。由于深度优先的算法特性，用递归会更加简洁。同时简单的深度优先在实际应用中也是需要做相应的变化的。下面我们就用leetcode中的例题来详细的说明下深度优先算法。

深度优先搜索的模板

深度优先搜索是有模板的，遇到了问题，我们是可以套用模板来进行解题的，这样可以极大的减轻代码分析的负担。

例题分析

岛屿的最大面积

  • 给你一个大小为 m x n 的二进制矩阵 grid 。
    岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
    岛屿的面积是岛上值为 1 的单元格的数目。
    计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

解析 ：
这个题目非常简单，我们可以从每一个点开始遍历，知道遍历到所有的1，那么就可以知道此次遍历得到的岛屿的面积，然后比较所有的面积即可。(需要注意的是注意边界条件)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int dfs(int** grid, int gridSize, int* gridColSize, int x, int y){
    if(x < 0 || y < 0 || x >= gridSize || y >= gridColSize[0] || grid[x][y]==0) return 0;

    grid[x][y] = 0;
    int di[4] = {0, 0, 1, -1};
    int dj[4] = {1, -1, 0, 0};
    int ans = 1;
    for(int i = 0; i<4; i++){
        int nextX = x + di[i];
        int nextY = y + dj[i];
        ans +=dfs(grid, gridSize, gridColSize, nextX, nextY);
    }
    return ans;

}

int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){
    int ans = 0;
    for(int i=0; i<gridSize; i++){
        for(int j=0; j<gridColSize[0]; j++){
            ans = fmax(ans, dfs(grid, gridSize, gridColSize, i, j));
        }
    }
    return ans;
}

上面的代码有没有什么问题？一定是有的，我们不需要遍历所有的节点，只需要遍历非0的节点就好了，因此有如下的优化：

1
2
3
4
5
6
7
8
9
10
11
int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){
    int ans = 0;
    for(int i=0; i<gridSize; i++){
        for(int j=0; j<gridColSize[0]; j++){
            if (grid[i][j] != 0) {
                ans = fmax(ans, dfs(grid, gridSize, gridColSize, i, j));
            }
        }
    }
    return ans;
}

加了这个判断条件，可以极大的减少遍历的节点数目

显示 Gitment 评论