本文详细介绍了深度优先遍历(深度优先)算法的基本概念、应用场景、实现方法及其优缺点,并通过多个代码示例展示了深度优先遍历在图和树的遍历中的实际应用。
深度优先遍历算法简介深度优先遍历(Depth-First Search, DFS)是一种树形或图形遍历算法,它从一个顶点开始,尽可能深入地探索一个尽可能深的分支路径,直到遇到一个未被访问的顶点,然后回溯到最近的一个未探索分支的顶点继续探索。该算法主要用于图和树的遍历,通过这种递归或迭代的方式,可以系统地访问图中每个顶点或树中每个节点。
深度优先遍历适用于多种场景,如图的遍历、树的遍历、迷宫问题、拓扑排序等。在实际应用中,深度优先遍历可以用于解决许多问题:
递归实现是深度优先遍历的一种常见方式。递归本质上是一个函数调用自身的过程,通过维护一个已访问集合来避免重复访问顶点。
def dfs_recursive(graph, vertex, visited): visited[vertex] = True print(vertex, end=' ') for neighbor in graph[vertex]: if not visited[neighbor]: dfs_recursive(graph, neighbor, visited) # 示例图 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } visited = {vertex: False for vertex in graph} dfs_recursive(graph, 'A', visited)
import java.util.*; public class DFSRecursive { private boolean[] visited; private Map<String, List<String>> graph; public DFSRecursive(Map<String, List<String>> graph) { this.graph = graph; visited = new boolean[graph.size()]; } public void dfsRecursive(String vertex) { visited[vertex] = true; System.out.print(vertex + " "); for (String neighbor : graph.get(vertex)) { if (!visited[neighbor]) { dfsRecursive(neighbor); } } } public static void main(String[] args) { Map<String, List<String>> graph = new HashMap<>(); graph.put("A", Arrays.asList("B", "C")); graph.put("B", Arrays.asList("A", "D", "E")); graph.put("C", Arrays.asList("A", "F")); graph.put("D", Arrays.asList("B")); graph.put("E", Arrays.asList("B", "F")); graph.put("F", Arrays.asList("C", "E")); DFSRecursive dfs = new DFSRecursive(graph); dfs.dfsRecursive("A"); } }
非递归实现通常使用栈来模拟递归的过程,避免递归调用带来的堆栈溢出问题。
def dfs_iterative(graph, start_vertex): visited = set() stack = [start_vertex] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) print(vertex, end=' ') for neighbor in graph[vertex]: if neighbor not in visited: stack.append(旴wing="true" neighbor) # 示例图 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } dfs_iterative(graph, 'A')
import java.util.*; public class DFSIterative { private Map<String, List<String>> graph; public DFSIterative(Map<String, List<String>> graph) { this.graph = graph; } public void dfsIterative(String startVertex) { boolean[] visited = new boolean[graph.size()]; Stack<String> stack = new Stack<>(); stack.push(startVertex); while (!stack.isEmpty()) { String vertex = stack.pop(); if (!visited[vertex]) { visited[vertex] = true; System.out.print(vertex + " "); for (String neighbor : graph.get(vertex)) { if (!visited[neighbor]) { stack.push(neighbor); } } } } } public static void main(String[] args) { Map<String, List<String>> graph = new HashMap<>(); graph.put("A", Arrays.asList("B", "C")); graph.put("B", Arrays.asList("A", "D", "E")); graph.put("C", Arrays.asList("A", "F")); graph.put("D", Arrays.asList("B")); graph.put("E", Arrays.asList("B", "F")); graph.put("F", Arrays.asList("C", "E")); DFSIterative dfs = new DFSIterative(graph); dfs.dfsIterative("A"); } }深度优先遍历的实际应用
深度优先遍历可以用于遍历图中的顶点和边。在图的遍历中,可以通过递归或迭代的方式遍历每个顶点。对于带权图,还可以使用深度优先搜索算法来寻找最短路径。
def dfs_graph(graph, start_vertex): visited = set() stack = [start_vertex] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) print(vertex, end=' ') for neighbor in graph[vertex]: 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_graph(graph, 'A')
深度优先遍历可以用于遍历树的每个节点。树的遍历包括前序遍历、中序遍历和后序遍历等。
def dfs_preorder(tree, root): if root is None: return print(root.value, end=' ') dfs_preorder(tree, root.left) dfs_preorder(tree, root.right) class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None # 示例树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) dfs_preorder(root, root)
def dfs_inorder(tree, root): if root is None: return dfs_inorder(tree, root.left) print(root.value, end=' ') dfs_inorder(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_inorder(root, root)
def dfs_postorder(tree, root): if root is None: return dfs_postorder(tree, root.left) dfs_postorder(tree, root.right) print(root.value, end=' ') # 示例树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) dfs_postorder(root, root)深度优先遍历的优缺点
def dfs_with_pruning(graph, start_vertex, goal_vertex): visited = set() stack = [(start_vertex, [])] while stack: vertex, path = stack.pop() if vertex not in visited: visited.add(vertex) print(vertex, end=' ') if vertex == goal_vertex: return path for neighbor in graph[vertex]: if neighbor not in visited: stack.append((neighbor, path + [neighbor])) # 示例图 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } path = dfs_with_pruning(graph, 'A', 'F') print(path)
迷宫问题可以通过深度优先遍历解决。给定一个迷宫,用0表示通路,1表示障碍,目标是找到从起点到终点的路径。
def dfs_maze(maze, start, end, path=None): if path is None: path = [] path.append(start) if start == end: return path for direction in [(0, 1), (1, 0), (0, -1), (-1, 0)]: new_position = (start[0] + direction[0], start[1] + direction[1]) if 0 <= new_position[0] < len(maze) and 0 <= new_position[1] < len(maze[0]) and maze[new_position[0]][new_position[1]] == 0 and new_position not in path: new_path = dfs_maze(maze, new_position, end, path) if new_path: return new_path path.pop() return None # 示例迷宫 maze = [ [0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0] ] start = (0, 0) end = (4, 4) path = dfs_maze(maze, start, end) print(path)