深度优先搜索算法（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_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为空。
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。
要求：计算网格中岛屿的数量。
注意：
- 岛屿总是被水包围，并且每座岛屿只能由水平方向 / 竖直方向上相邻的陆地连接形成。
- 此外，你可以假设该网格的四条边均被水包围。
如果把上下左右相邻的字符 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)