赞
踩
深度优先搜索算法(Depth First Search):英文缩写为 DFS。是一种用于搜索树或图的算法。所谓深度优先,就是说每次都尝试向更深的节点走。
深度优先搜索采用了回溯思想,该算法沿着树的深度遍历树的节点,会尽可能深的搜索树的分支。当节点 v
的所在边都己被探寻过,搜索将回溯到发现节点 v
的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。
在深度优先遍历的过程中,我们需要将当前遍历节点 v
的相邻节点暂时存储起来,以便于在回退的时候可以继续访问它们。遍历到的节点顺序符合「后进先出」的特点,这正是「递归」和「堆栈」所遵循的规律,所以深度优先搜索可以通过「递归」或者「堆栈」来实现。
接下来我们以一个无向图为例,演示一下深度优先搜索的过程。
我们用邻接字典的方式存储无向图结构,对应结构如下:
# 定义无向图结构
graph = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "D", "E"],
"D": ["B", "C", "E", "F"],
"E": ["C", "D"],
"F": ["D"]
}
该无向图对应的邻接字典表示:无向图中有 A
、B
、C
、D
、E
、F
共 6
个节点,其中与 A
节点相连的有 B
、C
两个节点,与 B
节点相连的有 A
、C
、D
三个节点,等等。
graph
为存储无向图的字典变量,visited
为标记访问节点的 set 集合变量。start
为当前遍历边的开始节点。def dfs_recursive(graph, start, visited):
为递归实现的深度优先搜索方法。start
标记为已访问,即将 start
节点放入 visited
中(visited.add(start)
)。start
,并对节点进行相关操作(看具体题目要求)。start
相连并构成边的节点 end
。
end
没有被访问过,则从 end
节点调用递归实现的深度优先搜索方法,即 dfs_recursive(graph, end, visited)
。def dfs_recursive(graph, start, visited):
# 标记节点
visited.add(start)
# 访问节点
print(start)
for end in graph[start]:
if end not in visited:
# 深度优先遍历节点
dfs_recursive(graph, end, visited)
start
为开始节点。定义 visited
为标记访问节点的 set 集合变量。定义 stack
用于存放临时节点的栈结构。visited = set(start)
,stack = [start]
。stack
栈顶元素 node_u
。node_u
相连并构成边的节点 node_v
。
node_v
没有被访问过,则:
node_v
,并对节点进行相关操作(看具体题目要求)。node_v
节点放入栈中,并标记访问,即 stack.append(node_v)
,visited.add(node_v)
。node_v
的循环。node_v
。node_u
相邻的节点都访问结束了,从栈顶弹出 node_u
,即 stack.pop()
。stack
为空。def dfs_stack(graph, start): print(start) # 访问节点 start visited = set(start) # 使用 visited 标记访问过的节点,先标记 start stack = [start] # 创建一个栈,并将 start 加入栈中 while stack: node_u = stack[-1] # 取栈顶元素 i = 0 while i < len(graph[node_u]): # 遍历栈顶元素,遇到未访问节点,访问节点并跳出。 node_v = graph[node_u][i] if node_v not in visited: # node_v 未访问过 print(node_v) # 访问节点 node_v stack.append(node_v) # 将 node_v 加入栈中 visited.add(node_v) # 标记为访问过 node_v break i += 1 if i == len(graph[node_u]): # node_u 相邻的节点都访问结束了,弹出 node_u stack.pop()
描述:给定一个由字符 '1'
(陆地)和字符 '0'
(水)组成的的二维网格 grid
。
要求:计算网格中岛屿的数量。
说明:
grid[i][j]
的值为 '0'
或 '1'
。示例:
输入:grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出:1 输入:grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出:3
如果把上下左右相邻的字符 '1'
看做是 1
个连通块,这道题的目的就是求解一共有多少个连通块。
使用深度优先搜索或者广度优先搜索都可以。
grid
。'1'
的元素,遍历其上下左右四个方向,并将该字符置为 0
,保证下次不会被重复遍历。0
。(i, j)
位置的元素来说,递归遍历的位置就是 (i - 1, j)
、(i, j - 1)
、(i + 1, j)
、(i, j + 1)
四个方向。每次遍历到底,统计数记录一次。class Solution: def dfs(self, grid, i, j): n = len(grid) m = len(grid[0]) if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] == '0': return 0 grid[i][j] = '0' self.dfs(grid, i + 1, j) self.dfs(grid, i, j + 1) self.dfs(grid, i - 1, j) self.dfs(grid, i, j - 1) def numIslands(self, grid: List[List[str]]) -> int: count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': self.dfs(grid, i, j) count += 1 return count
描述:以每个节点的邻接列表形式(二维列表)给定一个无向连通图,其中 adjList[i]
表示值为 i + 1
的节点的邻接列表,adjList[i][j]
表示值为 i + 1
的节点与值为 adjList[i][j]
的节点有一条边。
要求:返回该图的深拷贝。
说明:
100
。p
是节点 q
的邻居,那么节点 q
也必须是节点 p
的邻居。输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。
输入:adjList = [[2],[1]]
输出:[[2],[1]]
所谓深拷贝,就是构建一张与原图结构、值均一样的图,但是所用的节点不再是原图节点的引用,即每个节点都要新建。
可以用深度优先搜索或者广度优先搜索来做。
visitedDict
来存储原图中被访问过的节点和克隆图中对应节点,键值对为 原图被访问过的节点:克隆图中对应节点。class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return node visitedDict = dict() def dfs(node: 'Node') -> 'Node': if node in visitedDict: return visitedDict[node] clone_node = Node(node.val, []) visitedDict[node] = clone_node for neighbor in node.neighbors: clone_node.neighbors.append(dfs(neighbor)) return clone_node return dfs(node)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。