dfn深搜数

### 深度优先搜索算法（DFS）详解 #### 定义与基本概念 深度优先搜索算法英文全称为 Depth First Search (DFS)，中文简称深度优先搜索算法。该算法的特点是在搜索过程中沿每一条可能的路径尽可能深地向下探索，直至无法继续前进为止，并且每个节点仅被访问一次[^1]。 #### 工作原理 在执行 DFS 的时候，会从根结点出发，选择一个子节点进入下一层级并重复此过程；当遇到叶节点或者已经访问过的节点时，则回溯至上一层次尝试其他分支。这种机制确保了能够覆盖所有可达区域的同时不会陷入无限循环之中[^2]。 #### 实现方式 通常有两种方法来实现这一逻辑： - **递归法** 使用函数调用来模拟栈结构，在每次到达新位置后立即对其未处理的孩子依次发起相同的操作。 ```python def dfs_recursive(graph, node, visited=None): if visited is None: visited = set() visited.add(node) print(f"Visit {node}") for neighbor in graph[node]: if neighbor not in visited: dfs_recursive(graph, neighbor, visited) # Example usage with an adjacency list representation of a graph. graph_example = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': [], 'D': [], 'E': [] } dfs_recursive(graph_example, 'A') ``` - **迭代法** 利用手动管理的一个显式堆栈数据结构代替隐式的函数调用栈来进行同样的工作流程控制。 ```python from collections import deque def dfs_iterative(graph, start_node): stack = [start_node] visited = set() while stack: current_node = stack.pop() if current_node not in visited: print(f"Visit {current_node}") visited.add(current_node) # Add unvisited neighbors to the top of our stack for next_node in reversed(graph[current_node]): if next_node not in visited and next_node not in stack: stack.append(next_node) # Using same example as before but now using iterative approach instead. dfs_iterative(graph_example, 'A') ``` #### 应用场景 由于其特性决定了适合用于解决连通性检测、拓扑排序等问题以及寻找迷宫出口等实际应用场合中的最短路径查找任务。