深度优先算法

深度优先搜索

在之前的博客里面我们已经介绍了深度优先算法。实际上深度优先搜索一般可以用递归或者栈来实现。由于深度优先的算法特性,用递归会更加简洁。同时简单的深度优先在实际应用中也是需要做相应的变化的。下面我们就用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;
}

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