1. 所有可能的路径
class Solution:def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:def dfs(graph, result, path, root): #result 返回结果, path记录路径, root记录遍历到了第几个节点if root == len(graph) - 1: #如果遍历到最后一个节点，记录结果并返回result.append(path.copy()) returnfor i in graph[root]: #遍历每个节点下一个能到的下一个节点path.append(i) #path直接添加dfs(graph, result, path, i) #dfs递归, 输入的root直接变成i，也就是当前遍历的下一个path.pop() #回溯result = []path = [0] #初始化的时候path里已经有最初始的节点位置root = 0 #起始节点为0dfs(graph, result, path, root)return result实际上就是回溯算法，区别在于：之前做的回溯的题目一般是列表里面一个一个元素遍历，所以在递归的时候有一个start_index变量，控制选与不选当前元素。
而dfs搜索找下一个节点的时候，不用一个个遍历graph中的节点，而是只需要遍历当前节点能到达的节点，因为如果当前节点都到不了的节点，就没有必要往后遍历了。
因此递归的dfs的输入就变成了当前遍历的节点i
2. 岛屿数量
广搜 bfs版本
class Solution:def __init__(self):self.dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]self.count = 0def bfs(self, grid, visited, x, y): #广搜函数定义from collections import deque queue = deque() #初始化队列queue.append((x, y)) #加入起始节点visited[x][y] = True #标记起始节点为已访问while queue: #队列不为空进入循环curx, cury = queue.popleft() #取头节点for dx, dy in self.dir: #遍历四个方向nextx ,nexty = curx + dx, cury + dy if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]): #越界就跳过continueif grid[nextx][nexty] == "0": #如果本题中是海水也跳过continueif not visited[nextx][nexty]: #把所有陆地标记为已访问queue.append((nextx, nexty))visited[nextx][nexty] = Truedef numIslands(self, grid: List[List[str]]) -> int:visited = [[False] * len(grid[0]) for _ in range(len(grid))] #初始化访问数组for i in range(len(grid)):for j in range(len(grid[0])): #遍历gridif visited[i][j] == False and grid[i][j] == "1": #如果节点没被访问过以及是陆地self.count += 1 #计数+1self.bfs(grid, visited, i, j) #深搜一下把当前节点连通的所有陆地都标记为已访问return self.count3. 岛屿最大面积
class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) -> int:def bfs(grid, visited, x, y):from collections import deque q = deque() #初始化队列q.append((x, y)) #加入起点visited[x][y] = True #标记已遍历起点cnt = 1 #记录岛屿大小direction = [(-1, 0), (0, -1), (1, 0), (0, 1)] #四个方向while(q): #循环遍历队列中的节点curx, cury = q.popleft() #取出第一个节点for dx, dy in direction: #遍历四个方向nextx, nexty = curx + dx, cury + dyif nextx < 0 or nextx >= len(grid): #越界直接跳过continueif nexty < 0 or nexty >= len(grid[0]):continueif grid[nextx][nexty] == 0: #不是岛屿也直接跳过continueif not visited[nextx][nexty]: #是岛屿的部分q.append((nextx, nexty)) #加入节点visited[nextx][nexty] = True #标记为已访问cnt += 1 #面积加1return cnt #返回当前起点的岛屿大小result = 0visited = [[False] * len(grid[0]) for _ in range(len(grid))]for i in range(len(grid)): #遍历网格for j in range(len(grid[0])): if not visited[i][j] and grid[i][j] == 1: #让每个是岛屿的节点并且没被访问过的点作为起点去BFScur = bfs(grid, visited, i, j) #记录当前节点为起点的岛屿大小result = max(cur, result) #记录最大的岛屿大小return result
