本文介绍了深度优先搜索(DFS)的基本原理和应用场景,包括图的遍历、路径查找和拓扑排序等。文章还提供了使用递归和栈实现DFS的代码示例,并分析了DFS的优缺点以及其在复杂场景中的应用。
深度优先搜索(Depth-First Search,简称 DFS)是一种用于遍历或搜索树、图等数据结构的算法。DFS 的基本思想是从一个选定的起始节点出发,尽可能深地探索一条路径,直到无法继续前进时,再回溯到上一个节点,尝试其他可能的路径。这种搜索方式类似于从一个点出发,一直沿着一条路走到底,直到走到尽头,然后再回溯到上一个节点,重新选择其他路径。
深度优先搜索在许多场景中都有广泛的应用,常见的应用场景包括但不限于以下几种:
深度优先搜索可以通过不同的方式实现,常见的实现方式包括递归和栈两种。递归方法利用函数调用来实现回溯,而栈方法则通过手动管理栈来实现同样的效果。
递归是实现 DFS 的一种简便方法。递归方法的核心在于每次调用自身时都选择一个未访问的邻接节点,并且在无法继续前进时回溯。
下面是一个简单的递归实现 DFS 的代码示例,该代码使用了一个图(以邻接表形式表示)和一个队列来存储节点路径。
def dfs_recursive(graph, node, visited, path): # 标记当前节点为已访问,并添加到路径中 visited[node] = True path.append(node) # 递归访问所有相邻的未访问节点 for neighbor in graph[node]: if not visited[neighbor]: dfs_recursive(graph, neighbor, visited, path) # 当当前节点的邻接节点都已访问,回溯 return path # 示例图的邻接表表示 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } visited = {node: False for node in graph} path = [] result = dfs_recursive(graph, 'A', visited, path) print(result)
栈方法手动管理一个栈来保存当前路径。每次选择一个节点,将其所有未访问的邻接节点压入栈中,并将当前节点标记为已访问。当栈为空时,搜索结束。
下面是一个使用栈实现 DFS 的示例代码:
def dfs_iterative(graph, start): visited = set() # 存储已访问的节点 stack = [start] # 初始化栈,放入起始节点 while stack: node = stack.pop() # 从栈中取出节点 if node not in visited: visited.add(node) # 标记为已访问 print(node, end=' ') for neighbor in graph[node]: # 遍历所有邻接节点 if neighbor not in visited: stack.append(neighbor) # 将未访问的邻接节点压入栈中 # 示例图的邻接表表示 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } dfs_iterative(graph, 'A')
深度优先搜索的步骤相对简单且固定,主要包括以下几个关键步骤:
从当前节点选择一个未访问的邻接节点,进入该节点并重复上述步骤。如果当前节点的所有邻接节点都已访问,则回溯到上一个节点。
每次访问一个节点时,需要将该节点标记为已访问,以避免重复访问。在代码实现中,通常使用一个布尔值集合来记录访问状态。
假设我们有一个图,如下所示:
A -> B -> D | | v v C ---- E
具体步骤如下:
初始化:
visited
来记录已访问的节点。A
,并将其压入栈中。选择未访问的邻接节点:
A
,检查其邻接节点 B
和 C
。B
,将其压入栈中并标记为已访问。标记已访问的节点:
这个实例演示如何使用 DFS 遍历一个简单的图。假设我们有一个简单的图,如下所示:
A -> B -> C | | v v D -> E
下面是一个简单的 DFS 遍历该图的代码示例,使用递归实现:
def dfs_recursive_simple(graph, node, visited): visited[node] = True print(node, end=' ') for neighbor in graph[node]: if not visited[neighbor]: dfs_recursive_simple(graph, neighbor, visited) # 示例图的邻接表表示 graph_simple = { 'A': ['B', 'D'], 'B': ['A', 'C'], 'C': ['B'], 'D': ['A', 'E'], 'E': ['D'] } visited_simple = {node: False for node in graph_simple} dfs_recursive_simple(graph_simple, 'A', visited_simple)
这个实例演示如何使用 DFS 遍历一个复杂的图。假设我们有一个复杂的图,如下所示:
A -> B -> C -> D | | v v E -> F -> G
下面是一个复杂的 DFS 遍历该图的代码示例,使用栈实现:
def dfs_iterative_complex(graph, start): visited = set() stack = [start] while stack: node = stack.pop() if node not in visited: visited.add(node) print(node, end=' ') for neighbor in graph[node]: if neighbor not in visited: stack.append(neighbor) # 示例图的邻接表表示 graph_complex = { 'A': ['B', 'E'], 'B': ['A', 'C'], 'C': ['B', 'D', 'G'], 'D': ['C'], 'E': ['A', 'F'], 'F': ['E', 'G'], 'G': ['C', 'F'] } dfs_iterative_complex(graph_complex, 'A')
深度优先搜索适用于以下类型的问题:
虽然 DFS 有其优点,但也存在一些局限性:
在树结构中,DFS 可用于执行各种操作,如查找特定节点、计算树的高度、遍历树中的所有节点等。
下面是一个简单的树结构,并使用 DFS 遍历其所有节点的代码示例:
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def dfs_tree(root): if root is None: return print(root.val, end=' ') dfs_tree(root.left) dfs_tree(root.right) # 构建一个简单的二叉树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) dfs_tree(root)
在迷宫问题中,DFS 可以用于寻找从起点到终点的一条路径。迷宫可以用图来表示,每个方格是一个节点,方格之间的通路是节点之间的边。
下面是一个简单的迷宫问题,使用 DFS 寻找从起点到终点的路径的代码示例:
def is_valid(x, y, maze, visited): return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 1 and not visited[x][y] def dfs_maze(maze, start, end): dx = [-1, 1, 0, 0] # 方向数组,表示上下左右四个方向 dy = [0, 0, -1, 1] visited = [[False for _ in range(len(maze[0]))] for _ in range(len(maze))] stack = [(start[0], start[1], [start])] while stack: x, y, path = stack.pop() if (x, y) == end: print(f"Found path: {path}") return True visited[x][y] = True for i in range(4): next_x, next_y = x + dx[i], y + dy[i] if is_valid(next_x, next_y, maze, visited): stack.append((next_x, next_y, path + [(next_x, next_y)])) return False # 示例迷宫 maze = [ [1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1] ] start = (0, 0) end = (3, 3) dfs_maze(maze, start, end) `` 以上是深度优先搜索在树结构和迷宫问题中的应用示例,通过这些示例可以更好地理解 DFS 的实际应用场景和实现方式。