深度优先搜索算法(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"]
}
该无向图的结构如图左所示,图右为深度优先搜索的遍历路径。
其对应的动态演示图如下所示。
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_u
相连并构成边的节点node_v
。- 如果
node_v
没有被访问过,则将node_v
节点放入栈中,并标记访问,即stack.append(node_v)
,visited.add(node_v)
。
- 如果
- 重复步骤 3 ~ 5,直到
stack
为空。
def dfs_stack(graph, start):
visited = set(start)
stack = [start]
while stack:
node_u = stack.pop()
# 访问节点
print(node_u)
for node_v in graph[node_u]:
if node_v not in visited:
stack.append(node_v)
visited.add(node_v)
给定一个由 1
(陆地)和 0
(水)组成的的二维网格 grid
。
要求:计算网格中岛屿的数量。
注意:
- 岛屿总是被水包围,并且每座岛屿只能由水平方向 / 竖直方向上相邻的陆地连接形成。
- 此外,你可以假设该网格的四条边均被水包围。
如果把上下左右相邻的字符 1
看做是 1
个连通块,这道题的目的就是求解一共有多少个连通块。我们可以使用深度优先搜索来做。具体做法如下:
-
使用变量
count
统计连通块数目。然后遍历grid
。 -
对于
(i, j)
位置上的元素:- 如果
grid[i][j] == 1
,调用深度优先搜索方法,令统计变量 + 1。
- 如果
-
深度优先搜索方法:初始位置
(i, j)
位置是一块岛屿,目的是找到该点的岛屿边界。- 将其置为
0
(避免重复搜索)。然后从该点出发,递归遍历上、下、左、右四个方向,也就是递归遍历(i - 1, j)
、(i, j - 1)
、(i + 1, j)
、(i, j + 1)
四个方向。 - 终止条件:
(i, j)
超出矩阵范围。(i, j)
位置上是水,即grid[i][j] == 0
。
- 将其置为
-
最终统计出来的连通块数
count
就是我们要求的岛屿数量。
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
给定一个无向连通图中一个节点的引用。
要求:返回该图的深拷贝。
深拷贝的意思就是构建一张与原图结构、值均一样的图,但是所用的节点不再是原图节点的引用,即每个节点都要新建。
可以使用深度优先搜索遍历图的所有节点,并在遍历图的同时新建节点,并构建新图。具体做法如下:
- 使用字典变量
visited
存储访问过的节点,键值对为原节点 : 新节点
。 - 从
node
节点开始,调用深度优先搜索方法。- 如果
node
节点在visited
中,则返回visited
中存储的新节点,即visited[node]
。 - 新建复制节点
clone_node
,赋值为node.val
。 - 将其加入到
visited
中,即visited[node] = clone_node
。 - 遍历
node
节点的相邻节点,并从相邻节点开始,递归调用深度优先搜索方法。 - 最后返回
clone_node
。
- 如果
class Solution:
def dfs(self, node: 'Node', visited) -> 'Node':
if node in visited:
return visited[node]
clone_node = Node(node.val, [])
visited[node] = clone_node
for neighbor in node.neighbors:
clone_node.neighbors.append(self.dfs(neighbor, visited))
return clone_node
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return node
visited = dict()
return self.dfs(node, visited)