算法之深度优先搜索

发表于 | 更新于: | 分类于 ， | | 阅读数
字数统计: 1.7k | 阅读时长 ≈ 8

DFS基本思想

  1. 本质是遍历决策树
  2. 关注路径、选择列表、结束条件
  3. 结合回溯：重点是撤销选择
1
2
3
4
5
6
7
8
9
10
result = []
def dfs(路径, 选择列表):
    if 满足结束条件:
        result.append(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        dfs(路径, 选择列表)
        撤销选择

二叉树的DFS

对于二叉树，我们一般这样做DFS：

1
2
3
4
5
6
7
def dfs(root):
   	# 判断 base case
    if not root:return
    
    # 访问两个相邻结点：左子结点、右子结点
    dfs(root.left)
    dfs(root.right)

更多二叉树的遍历，可以看我的另一篇文章：二叉树的遍历

网格类问题的DFS

类比二叉树的DFS，我们可以总结出网格类问题的DFS：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
row,col=len(grid),len(grid[0])

def dfs(grid,r,c):
    # 判断 base case: 如果坐标 (r, c) 超出了网格范围，直接返回
    if not inArea(grid, r, c):return
    
    # 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c)
    dfs(grid, r + 1, c)
    dfs(grid, r, c - 1)
    dfs(grid, r, c + 1)


# 判断坐标 (r, c) 是否在网格中
def inArea(grid, r, c):
    return 0 <= r < row and  0 <= c < col

避免重复遍历：

我们可以创建一个seen或visited来记录已访问过的网格

1
2
3
4
5
6
7
8
row,col=len(grid),len(grid[0])
seen=[[0 for _ in range(col)] for _ in range(row)]

def dfs(grid,r,c):
    if not inArea(grid, r, c):return
    if seen[r][c]:return
    seen[r][c]=1
    ………………

总结模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
row,col=len(grid),len(grid[0])
seen=[[0 for _ in range(col)] for _ in range(row)]
road=[(0,1),(0,-1),(1,0),(-1,0)]

def dfs(i,j):
    if not 0<=i<row or not 0<=j<col:return
    if not grid[i][j]:return
    if seen[i][j]:return 
    seen[i][j]=1

    for x,y in road:
        dfs(i+x,j+y)

for i in range(row):
    for j in range(col):
        if grid[i][j]:
            dfs(i,j)

需要注意grid[i][j]为(0,1)或(‘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
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row,col=len(grid),len(grid[0])
        seen=[[0 for _ in range(col)] for _ in range(row)]
        road=[(0,1),(0,-1),(1,0),(-1,0)]

        def dfs(i,j):
            if not 0<=i<row or not 0<=j<col:return 
            if seen[i][j]:return
            if grid[i][j]=='0':return
            seen[i][j]=1
        
            for m,n in road:
                dfs(i+m,j+n)
            
        
        res=0
        for i in range(row):
            for j in range(col):
                if grid[i][j]=='1' and not seen[i][j]:
                    dfs(i,j)
                    res+=1
        return res

岛屿的最大面积

注意结束搜索时return 0 且dfs返回：1+dfs(上)+dfs(下)+dfs(左)+dfs(右)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        row,col=len(grid),len(grid[0])
        seen=[[0 for _ in range(col)] for _ in range(row)]
        road=[(1,0),(-1,0),(0,1),(0,-1)]

        def dfs(i,j):
            if not 0<=i<row or not 0<=j<col:return 0
            if not grid[i][j]:return 0
            if seen[i][j]:return 0
            seen[i][j]=1
            
            tmp=1	# 注意tmp不是0
            for m,n in road:
                tmp+=dfs(i+m,j+n)
            return tmp
        
        res=0
        for i in range(row):
            for j in range(col):
                if grid[i][j]:
                    res=max(res,dfs(i,j))

        return res

最大人工岛

做两次DFS，第一次标记不同岛屿及其面积；第二次对每一个海洋，寻找其能串联的不同岛屿的面积之和

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n=len(grid)
        if 0 not in [i for j in grid for i in j]:return n*n # 【全是岛屿】的情况
        seen=[[0 for _ in range(n)] for _ in range(n)]
        road=[(0,1),(0,-1),(1,0),(-1,0)]

        def dfs(i,j,cnt):
            if not 0<=i<n or not 0<=j<n:return 0
            if not grid[i][j]:return 0
            if seen[i][j]:return 0
            seen[i][j]=cnt

            tmp=1
            for x,y in road:
                tmp+=dfs(i+x,j+y,cnt)
            return tmp

        cnt=2   # 标记不同岛屿
        mark={0:0} # 记录每个岛屿面积;初始为{0,0}是为了预防 【全是海洋】的情况
        for i in range(n):
            for j in range(n):
                if grid[i][j]:
                    area=dfs(i,j,cnt)
                    if area:mark.setdefault(cnt,area)   
                    cnt+=1
        
        # 对每一个海洋，最多能串联的岛屿面积为其(上下左右)的不同岛屿的面积之和+1
        res=0
        for i in range(n):
            for j in range(n):
                if not grid[i][j]:
                    tmp=set()   # 去除相同岛屿
                    for x,y in road:
                        if 0<=i+x<n and  0<=j+y<n:
                            tmp.add(seen[i+x][j+y])
                    area=1
                    for t in tmp:
                        area+=mark[t]
                    
                    res=max(res,area)
        return res

岛屿的周长

岛屿的周长，实际上就是由dfs停止搜索时的遇到的边界构成：

  • 当遇到边界而停止搜索时，岛屿增加一条边
  • 当遇到海洋而停止搜索时，岛屿增加一条边
  • 当遇到已搜而停止搜索时，岛屿不增加边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        row,col=len(grid),len(grid[0])
        seen=[[0 for _ in range(col)] for _ in range(row)]
        road=[(0,1),(0,-1),(1,0),(-1,0)]

        def dfs(i,j):
            if not 0<=i<row or not 0<=j<col:return 1
            if not grid[i][j]:return 1
            if seen[i][j]:return 0
            seen[i][j]=1

            tmp=0
            for x,y in road:
                tmp+=dfs(i+x,j+y)
            return tmp
        
        for i in range(row):
            for j in range(col):
                if grid[i][j]:
                    return dfs(i,j)

统计子岛屿

与岛屿数量是一样的做法，只不过需要再用path记录每个岛屿包含的格子

当一个岛屿的所有格子都被包含在grid1中时,res+=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
26
27
28
29
30
class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        row,col=len(grid1),len(grid1[0])
        seen=[[0 for _ in range(col)] for _ in range(row)]
        road=[(0,1),(0,-1),(1,0),(-1,0)]

        def dfs(i,j,path):
            if not 0<=i<row or not 0<=j<col:return 
            if seen[i][j]:return
            if not grid2[i][j]:return
            seen[i][j]=1
            path.append((i,j))

            for m,n in road:
                dfs(i+m,j+n,path)
            
        
        res=0
        for i in range(row):
            for j in range(col):
                if grid2[i][j] and not seen[i][j]:
                    path=[]
                    dfs(i,j,path)
                    flag=1
                    for p in path:
                        if not grid1[p[0]][p[1]]:
                            flag=0
                            break
                    res+=flag
        return res

统计封闭岛屿的数目

从边界退出的，不是封闭岛屿

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
26
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        row,col=len(grid),len(grid[0])
        seen=[[0 for _ in range(col)] for _ in range(row)]
        road=[(0,1),(0,-1),(1,0),(-1,0)]

        def dfs(i,j,flag):
            if not 0<=i<row or not 0<=j<col:
                flag[0]=0
                return 
            if seen[i][j]:return
            if grid[i][j]:return
            seen[i][j]=1
        
            for m,n in road:
                dfs(i+m,j+n,flag)
            
        
        res=0
        for i in range(row):
            for j in range(col):
                if not grid[i][j] and not seen[i][j]:
                    flag=[1]
                    dfs(i,j,flag)
                    res+=flag[0]
        return res

可以试试用变量flag=1代替flag=[1]，看看结果对不对

不要打赏，只求关注呀QAQ