1. 深度优先搜索简介
深度优先搜索算法(Depth First Search):英文缩写为 DFS。是一种用于搜索树或图的算法。所谓深度优先,就是说每次都尝试向更深的节点走。
深度优先搜索采用了回溯思想,该算法沿着树的深度遍历树的节点,会尽可能深的搜索树的分支。当节点v
的所在边都己被探寻过,搜索将回溯到发现节点v
的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。
在深度优先遍历的过程中,我们需要将当前遍历节点v
的相邻节点暂时存储起来,以便于在回退的时候可以继续访问它们。遍历到的节点顺序符合「后进先出」的特点,这正是「递归」和「堆栈」所遵循的规律,所以深度优先搜索可以通过「递归」或者「堆栈」来实现。
2. 深度优先搜索过程演示
接下来我们以一个无向图为例,演示一下深度优先搜索的过程。
我们用邻接字典的方式存储无向图结构,对应结构如下:
# 定义无向图结构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
三个节点,等等。
该无向图的结构如图左所示,其深度优先搜索的遍历路径如图右所示。
其深度优先搜索的遍历过程如下动态图所示。
3. 基于递归实现的深度优先搜索
3.1 基于递归实现的深度优先搜索实现步骤
定义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)
。
3.2 基于递归实现的深度优先搜索实现代码
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)
4. 基于堆栈实现的深度优先搜索
4.1 基于堆栈实现的深度优先搜索实现步骤
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()
。
重复步骤 4 ~ 6,直到stack
为空。
4.2 基于堆栈实现的深度优先搜索实现代码
def dfs_stack(graph, start):print(start) # 访问节点 startvisited = set(start)# 使用 visited 标记访问过的节点,先标记 startstack = [start] # 创建一个栈,并将 start 加入栈中while stack:node_u = stack[-1] # 取栈顶元素i = 0while i < len(graph[node_u]): # 遍历栈顶元素,遇到未访问节点,访问节点并跳出。node_v = graph[node_u][i]if node_v not in visited: # node_v 未访问过print(node_v) # 访问节点 node_vstack.append(node_v) # 将 node_v 加入栈中visited.add(node_v)# 标记为访问过 node_vbreaki += 1if i == len(graph[node_u]): # node_u 相邻的节点都访问结束了,弹出 node_ustack.pop()
5. 深度优先搜索应用
5.1 岛屿数量
5.1.1 题目链接
200. 岛屿数量 - 力扣(LeetCode)
5.1.2 题目大意
描述:给定一个由字符'1'
(陆地)和字符'0'
(水)组成的的二维网格grid
。
要求:计算网格中岛屿的数量。
说明:
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
$m == grid.length$。
$n == grid[i].length$。
$1 \le m, n \le 300$。
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
5.1.3 解题思路
如果把上下左右相邻的字符'1'
看做是1
个连通块,这道题的目的就是求解一共有多少个连通块。
使用深度优先搜索或者广度优先搜索都可以。
思路 1:深度优先搜索
遍历grid
。
对于每一个字符为'1'
的元素,遍历其上下左右四个方向,并将该字符置为0
,保证下次不会被重复遍历。
如果超出边界,则返回0
。
对于(i, j)
位置的元素来说,递归遍历的位置就是(i - 1, j)
、(i, j - 1)
、(i + 1, j)
、(i, j + 1)
四个方向。每次遍历到底,统计数记录一次。
最终统计出深度优先搜索的次数就是我们要求的岛屿数量。
思路 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 0grid[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 = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == '1':self.dfs(grid, i, j)count += 1return count
思路 1:复杂度分析
时间复杂度:$O(m \times n)$。其中 $m$ 和 $n$ 分别为行数和列数。
空间复杂度:$O(m \times n)$。
5.2 克隆图
5.2.1 题目链接
133. 克隆图 - 力扣(LeetCode)
5.2.2 题目大意
描述:以每个节点的邻接列表形式(二维列表)给定一个无向连通图,其中adjList[i]
表示值为i + 1
的节点的邻接列表,adjList[i][j]
表示值为i + 1
的节点与值为adjList[i][j]
的节点有一条边。
要求:返回该图的深拷贝。
说明:
节点数不超过100
。
每个节点值 $Node.val$ 都是唯一的,$1 \le Node.val \le 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]]
5.2.3 解题思路
所谓深拷贝,就是构建一张与原图结构、值均一样的图,但是所用的节点不再是原图节点的引用,即每个节点都要新建。
可以用深度优先搜索或者广度优先搜索来做。
思路 1:深度优先搜索
使用哈希表visitedDict
来存储原图中被访问过的节点和克隆图中对应节点,键值对为 原图被访问过的节点:克隆图中对应节点。
从给定节点开始,以深度优先搜索的方式遍历原图。
如果当前节点被访问过,则返回隆图中对应节点。
如果当前节点没有被访问过,则创建一个新的节点,并保存在哈希表中。
遍历当前节点的邻接节点列表,递归调用当前节点的邻接节点,并将其放入克隆图中对应节点。
递归结束,返回克隆节点。
思路 1:代码
class Solution:def cloneGraph(self, node: 'Node') -> 'Node':if not node:return nodevisitedDict = dict()def dfs(node: 'Node') -> 'Node':if node in visitedDict:return visitedDict[node]clone_node = Node(node.val, [])visitedDict[node] = clone_nodefor neighbor in node.neighbors:clone_node.neighbors.append(dfs(neighbor))return clone_nodereturn dfs(node)
思路 1:复杂度分析
时间复杂度:$O(n)$。其中 $n$ 为图中节点数量。
空间复杂度:$O(n)$。