深度优先搜索算法

深度优先搜索算法 (DFS)

深度优先搜索 (Depth-First Search) 是一种用于遍历或搜索树或图数据结构的算法。该算法从起始顶点出发，沿着一条路径尽可能深地探索，直到无法继续（遇到死胡同或已访问顶点），然后回溯到上一个分叉点，继续探索其他未访问的分支。DFS 天然适合使用递归实现，也可借助栈进行迭代模拟。

算法步骤（递归版）

1. 标记与处理：访问起始顶点 v，将其标记为“已访问”，并进行所需处理（如记录结果）。
2. 递归深入：依次检查 v 的每一个邻接顶点 w。
   • 若 w 未被访问，则以 w 为新起点，递归执行步骤 1、2。
3. 自然回溯：当 v 的所有邻接点均被访问过，当前递归调用结束，自动返回上一层调用，继续探索上一层未完成的邻接点。
4. 终止条件：当所有从起始顶点可达的顶点均被访问后，算法结束。

def DFS(self, start):
    visited = set()
    result = []
    
    def dfs(v):
        # 1. 标记当前节点为已访问并记录
        visited.add(v)
        result.append(v)
        
        # 2. 遍历所有邻接节点
        for neighbor in self.adj[v]:
            # 3. 如果未访问，递归深入
            if neighbor not in visited:
                dfs(neighbor) # 修正：此处应为 dfs，而非 def
    
    # 启动递归
    dfs(start)
    return result

算法步骤（迭代版，显式栈）

1. 初始化：创建一个空栈 S，一个集合 visited 记录已访问顶点。
2. 入栈启动：将起始顶点压入栈中。
3. 循环处理（当栈非空）：
   • 弹出栈顶顶点 v。
   • 若 v 尚未访问：
     • 标记 v 为已访问，处理 v。
     • 将 v 的所有未访问邻接顶点（注意：通常为了保持与递归一致的顺序，需逆序压入栈，但非必须）压入栈中。
4. 结束：栈空时，从起点可达的顶点均被遍历。

def DFS_Iterative(self, start):
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        v = stack.pop()
        
        if v not in visited:
            # 标记并处理当前节点
            visited.add(v)
            result.append(v)
            
            # 将未访问的邻接点压入栈 (逆序压入以模拟递归的顺序)
            # 注意：这里需要逆序遍历邻接表，以保证先访问最先定义的邻居
            for neighbor in reversed(self.adj[v]): 
                if neighbor not in visited:
                    stack.append(neighbor)
                    
    return result

复杂度分析

指标	复杂度	说明
时间复杂度	$O(V + E)$	$V$ 为顶点数，$E$ 为边数。每个顶点和每条边最多被访问一次。
空间复杂度	$O(V)$	主要用于存储 visited 集合以及递归调用栈（递归版）或显式栈（迭代版）的开销。最坏情况下栈深度为 $V$。

应用场景

DFS 是解决连通性问题和路径搜索问题的基石，广泛应用于以下场景：

1. 路径搜索：
   • 在迷宫求解中寻找出口。
   • 检查图中两点之间是否存在路径。
2. 拓扑排序：
   • 用于任务调度，确定有向无环图 (DAG) 中任务的执行顺序。
3. 连通分量检测：
   • 寻找图中的所有连通块（如社交网络中的圈子分析）。
   • 判断图是否为二分图。
4. 回溯算法 (Backtracking)：
   • 解决 N 皇后问题、数独求解、全排列生成等。DFS 提供了探索所有可能性的基础框架，回溯则是在 DFS 过程中进行剪枝和状态恢复。
5. 树的遍历：
   • 前序、中序、后序遍历本质上都是深度优先搜索。

相关

TABLE without id file.link AS "题目名称", 数据结构,date
FROM #LeetCode 
WHERE contains(数据结构, "DFS")
SORT file.mtime DESC