贵州黔东南双控体系建设网站,建设专业网站哪家技术好,展示型网站,网站建设手机app文章目录 1 DFS和BFS797. 所有可能的路径200. 岛屿数量 1 DFS和BFS
深度优先遍历一般采用回溯算法进行解决。回溯算法#xff0c;其实就是dfs的过程。
void dfs(参数) {处理节点dfs(图#xff0c;选择的节点); // 递归回溯#xff0c;撤销处理结果
}广度优先搜索理解为层次… 文章目录 1 DFS和BFS797. 所有可能的路径200. 岛屿数量 1 DFS和BFS
深度优先遍历一般采用回溯算法进行解决。回溯算法其实就是dfs的过程。
void dfs(参数) {处理节点dfs(图选择的节点); // 递归回溯撤销处理结果
}广度优先搜索理解为层次遍历。
797. 所有可能的路径 直接DFS就好了有向无环图甚至不用设置一个visited数组来判断某个点是否访问过。
class Solution:def __init__(self):self.result_list []def allPathsSourceTarget(self, graph: List[List[int]]) - List[List[int]]:path [0]visited [0] * len(graph)self.traverse(0, len(graph), graph, visited, path)return self.result_listdef traverse(self, i, n, graph, visited, path):if i n-1:self.result_list.append(path.copy()) # 注意要copyreturnfor j in graph[i]:if visited[j] 0:path.append(j)self.traverse(j, n, graph, visited, path) # dfspath.pop() # 回溯return 200. 岛屿数量 class Solution:def dfs(self, i, j, visited, grid, m, n):visited[i][j] 1nbrs [(i, j-1), (i-1, j), (i1, j), (i, j1)]for nbr in nbrs:if 0 nbr[0] m and 0 nbr[1] n and visited[nbr[0]][nbr[1]] 0 and grid[nbr[0]][nbr[1]] 1:self.dfs(nbr[0], nbr[1], visited, grid, m, n)def numIslands(self, grid: List[List[str]]) - int:# 每次搜索到一个连通分量后重新从下一个点开始f即可total_num 0m, n len(grid), len(grid[0])visited [[0 for _ in range(n)] for _ in range(m)]for i in range(m):for j in range(n):if visited[i][j] 0 and grid[i][j] 1:total_num 1self.dfs(i,j,visited,grid,m,n)return total_num
