01. 图的深度优先搜索知识
01. 图的深度优先搜索知识
1. 深度优先搜索简介
深度优先搜索算法(Depth First Search):英文缩写为 DFS,是一种用于搜索树或图结构的算法。深度优先搜索算法采用了回溯思想,从起始节点开始,沿着一条路径尽可能深入地访问节点,直到无法继续前进时为止,然后回溯到上一个未访问的节点,继续深入搜索,直到完成整个搜索过程。
深度优先搜索算法中所谓的深度优先,就是说优先沿着一条路径走到底,直到无法继续深入时再回头。
在深度优先遍历的过程中,我们需要将当前遍历节点
2. 深度优先搜索算法步骤
接下来我们以一个无向图为例,介绍一下深度优先搜索的算法步骤。
- 选择起始节点
,并将其标记为已访问。 - 检查当前节点是否为目标节点(看具体题目要求)。
- 如果当前节点
是目标节点,则直接返回结果。 - 如果当前节点
不是目标节点,则遍历当前节点 的所有未访问邻接节点。 - 对每个未访问的邻接节点
,从节点 出发继续进行深度优先搜索(递归)。 - 如果节点
没有未访问的相邻节点,回溯到上一个节点,继续搜索其他路径。 - 重复
步骤,直到遍历完整个图或找到目标节点为止。
::: tabs#DFS
@tab <1>
@tab <2>
@tab <3>
@tab <4>
@tab <5>
@tab <6>
:::
3. 基于递归实现的深度优先搜索
3.1 基于递归实现的深度优先搜索算法步骤
深度优先搜索算法可以通过递归来实现,以下是基于递归实现的深度优先搜索算法步骤:
- 定义
为存储无向图的嵌套数组变量, 为标记访问节点的集合变量。 为当前遍历边的开始节点。定义def dfs_recursive(graph, u, visited):
为递归实现的深度优先搜索方法。 - 选择起始节点
,并将其标记为已访问,即将节点 放入 中(visited.add(u)
)。 - 检查当前节点
是否为目标节点(看具体题目要求)。 - 如果当前节点
是目标节点,则直接返回结果。 - 如果当前节点
不是目标节点,则遍历当前节点 的所有未访问邻接节点。 - 对每个未访问的邻接节点
,从节点 出发继续进行深度优先搜索(递归),即调用dfs_recursive(graph, v, visited)
。 - 如果节点
没有未访问的相邻节点,则回溯到最近访问的节点,继续搜索其他路径。 - 重复
步骤,直到遍历完整个图或找到目标节点为止。
3.2 基于递归实现的深度优先搜索实现代码
class Solution:
def dfs_recursive(self, graph, u, visited):
print(u) # 访问节点
visited.add(u) # 节点 u 标记其已访问
for v in graph[u]:
if v not in visited: # 节点 v 未访问过
# 深度优先搜索遍历节点
self.dfs_recursive(graph, v, visited)
graph = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "D", "E"],
"D": ["B", "C", "E", "F"],
"E": ["C", "D"],
"F": ["D", "G"],
"G": []
}
# 基于递归实现的深度优先搜索
visited = set()
Solution().dfs_recursive(graph, "A", visited)
4. 基于堆栈实现的深度优先搜索
4.1 基于堆栈实现的深度优先搜索算法步骤
深度优先搜索算法除了基于递归实现之外,还可以基于堆栈来实现。同时,为了防止多次遍历同一节点,在使用栈存放节点访问记录时,我们将「当前节点」以及「下一个将要访问的邻接节点下标」一同存入栈中,从而在出栈时,可以通过下标直接找到下一个邻接节点,而不用遍历所有邻接节点。
以下是基于堆栈实现的深度优先搜索的算法步骤:
- 定义
为存储无向图的嵌套数组变量, 为标记访问节点的集合变量。 为当前遍历边的开始节点。定义 用于存放节点访问记录的栈结构。 - 选择起始节点
,检查当前节点 是否为目标节点(看具体题目要求)。 - 如果当前节点
是目标节点,则直接返回结果。 - 如果当前节点
不是目标节点,则将节点 以及节点 下一个将要访问的邻接节点下标 放入栈中,并标记为已访问,即stack.append([u, 0])
,visited.add(u)
。 - 如果栈不为空,取出
栈顶元素节点 ,以及节点 下一个将要访问的邻接节点下标 。 - 根据节点
和下标 ,取出将要遍历的未访问过的邻接节点 。 - 将节点
以及节点 u 的下一个邻接节点下标 放入栈中。 - 访问节点
,并对节点进行相关操作(看具体题目要求)。 - 将节点
以及节点 下一个邻接节点下标 放入栈中,并标记为已访问,即stack.append([v, 0])
,visited.add(v)
。 - 重复步骤
,直到 栈为空或找到目标节点为止。
4.2 基于堆栈实现的深度优先搜索实现代码
class Solution:
def dfs_stack(self, graph, u):
print(u) # 访问节点 u
visited, stack = set(), [] # 使用 visited 标记访问过的节点, 使用栈 stack 存放临时节点
stack.append([u, 0]) # 将节点 u,节点 u 的下一个邻接节点下标放入栈中,下次将遍历 graph[u][0]
visited.add(u) # 将起始节点 u 标记为已访问
while stack:
u, i = stack.pop() # 取出节点 u,以及节点 u 下一个将要访问的邻接节点下标 i
if i < len(graph[u]):
v = graph[u][i] # 取出邻接节点 v
stack.append([u, i + 1]) # 下一次将遍历 graph[u][i + 1]
if v not in visited: # 节点 v 未访问过
print(v) # 访问节点 v
stack.append([v, 0]) # 下一次将遍历 graph[v][0]
visited.add(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", "G"],
"G": []
}
# 基于堆栈实现的深度优先搜索
Solution().dfs_stack(graph, "A")
5. 深度优先搜索应用
5.1 岛屿数量
5.1.1 题目链接
5.1.2 题目大意
描述:给定一个由字符 '1'
(陆地)和字符 '0'
(水)组成的的二维网格 grid
。
要求:计算网格中岛屿的数量。
说明:
- 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
- 此外,你可以假设该网格的四条边均被水包围。
。 。 。 的值为'0'
或'1'
。
示例:
- 示例 1:
输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1
- 示例 2:
输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出:3
5.1.3 解题思路
如果把上下左右相邻的字符 '1'
看做是 1
个连通块,这道题的目的就是求解一共有多少个连通块。
使用深度优先搜索或者广度优先搜索都可以。
思路 1:深度优先搜索
- 遍历
。 - 对于每一个字符为
'1'
的元素,遍历其上下左右四个方向,并将该字符置为'0'
,保证下次不会被重复遍历。 - 如果超出边界,则返回
。 - 对于
位置的元素来说,递归遍历的位置就是 、 、 、 四个方向。每次遍历到底,统计数记录一次。 - 最终统计出深度优先搜索的次数就是我们要求的岛屿数量。
思路 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
思路 1:复杂度分析
- 时间复杂度:
。其中 和 分别为行数和列数。 - 空间复杂度:
。
5.2 克隆图
5.2.1 题目链接
5.2.2 题目大意
描述:以每个节点的邻接列表形式(二维列表)给定一个无向连通图,其中
要求:返回该图的深拷贝。
说明:
- 节点数不超过
。 - 每个节点值
都是唯一的, 。 - 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
- 由于图是无向的,如果节点
是节点 的邻居,那么节点 也必须是节点 的邻居。 - 图是连通图,你可以从给定节点访问到所有节点。
示例:
输入: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]]
5.2.3 解题思路
所谓深拷贝,就是构建一张与原图结构、值均一样的图,但是所用的节点不再是原图节点的引用,即每个节点都要新建。
可以用深度优先搜索或者广度优先搜索来做。
思路 1:深度优先搜索
- 使用哈希表
来存储原图中被访问过的节点和克隆图中对应节点,键值对为「原图被访问过的节点:克隆图中对应节点」。 - 从给定节点开始,以深度优先搜索的方式遍历原图。
- 如果当前节点被访问过,则返回隆图中对应节点。
- 如果当前节点没有被访问过,则创建一个新的节点,并保存在哈希表中。
- 遍历当前节点的邻接节点列表,递归调用当前节点的邻接节点,并将其放入克隆图中对应节点。
- 递归结束,返回克隆节点。
思路 1:代码
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)
思路 1:复杂度分析
- 时间复杂度:
。其中 为图中节点数量。 - 空间复杂度:
。
参考资料
- 【文章】深度优先搜索 - LeetBook - 力扣(LeetCode)
- 【文章】算法数据结构:深度优先搜索(DFS) - 掘金
- 【文章】Python 图的 BFS 与 DFS - 黄蜜桃的博客 - CSDN 博客
- 【文章】图的深度优先遍历(递归、非递归;邻接表,邻接矩阵)_zjq_smile 的博客 - CSDN博客
- 【题解】200. 岛屿数量(DFS / BFS) - 岛屿数量 - 力扣(LeetCode)
来源:https://github.com/itcharge/LeetCode-Py