dfs.md

深度优先搜索 (DFS) 教案

1. 算法基础理论资料

算法定义与背景

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法从根节点开始，沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

DFS由Charles Pierre Trémaux在19世纪设计，是图论中经典的基础算法之一。

问题定义

在图或树数据结构中系统地访问所有节点，确保每个节点恰好被访问一次。

数学基础

基于图论和递归的数学概念。

2. 算法详细描述

算法思想

从起始节点开始，沿着一条路径尽可能深入地访问节点，直到不能再深入为止，然后回溯到上一个节点，继续探索其他未访问的路径，直到所有节点都被访问过。

算法步骤

1. 从起始节点开始，标记该节点为已访问；
2. 对于当前节点的每个未访问过的邻接节点，递归地执行深度优先搜索；
3. 如果当前节点没有未访问的邻接节点，则回溯到上一个节点；
4. 重复步骤2-3，直到所有节点都被访问。

伪代码

算法 DFS(graph, startVertex)
输入：图graph，起始顶点startVertex
输出：节点的访问顺序

算法 DFS_Recursive(vertex)
    标记vertex为已访问
    访问vertex
    对于vertex的每个邻接节点neighbor
        如果neighbor未被访问
            DFS_Recursive(neighbor)

算法 DFS_Iterative(graph, startVertex)
    创建一个栈stack
    标记startVertex为已访问
    将startVertex压入stack
    while stack不为空
        vertex = 从stack弹出元素
        访问vertex
        对于vertex的每个邻接节点neighbor
            如果neighbor未被访问
                标记neighbor为已访问
                将neighbor压入stack

3. 算法实现

Python实现

# 递归实现
def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(vertex)
    print(vertex, end=' ')
    
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

# 迭代实现
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            
            # 将邻接节点加入栈中（逆序添加以保证访问顺序）
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return visited

Java实现

import java.util.*;

// 递归实现
public static void dfsRecursive(Map<Integer, List<Integer>> graph, int vertex, Set<Integer> visited) {
    visited.add(vertex);
    System.out.print(vertex + " ");
    
    for (int neighbor : graph.getOrDefault(vertex, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

// 迭代实现
public static void dfsIterative(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();
    
    stack.push(start);
    
    while (!stack.isEmpty()) {
        int vertex = stack.pop();
        
        if (!visited.contains(vertex)) {
            visited.add(vertex);
            System.out.print(vertex + " ");
            
            // 将邻接节点加入栈中（逆序添加以保证访问顺序）
            List<Integer> neighbors = graph.getOrDefault(vertex, new ArrayList<>());
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

4. 复杂度分析

时间复杂度

• 邻接表表示：O(V + E)，其中V是顶点数，E是边数
• 邻接矩阵表示：O(V²)

空间复杂度

• 递归版本：O(V) - 递归调用栈的深度
• 迭代版本：O(V) - 显式栈的空间

数学证明

在邻接表表示中，每个顶点和每条边都只会被访问常数次，因此时间复杂度为O(V + E)。

5. 示例与案例

简单示例

图的邻接表表示：

0: [1, 2]
1: [0, 3, 4]
2: [0]
3: [1]
4: [1]

从节点0开始DFS遍历，可能的访问顺序：0 -> 1 -> 3 -> 4 -> 2

复杂案例

1. 处理大型稀疏图
2. 处理有环图
3. 在树结构中的应用

边界条件

• 空图
• 只有一个节点的图
• 不连通的图
• 有向图和无向图

6. 算法可视化

可以通过动画演示DFS如何沿着一条路径深入，遇到死胡同时如何回溯，以及如何访问所有可达节点。

7. 优缺点分析

优势

• 内存需求相对较低（相对于BFS）
• 可以用于检测图中的环
• 可以用于拓扑排序
• 可以用于寻找强连通分量
• 实现相对简单

局限性

• 可能会陷入很深的路径，导致栈溢出
• 不一定能找到最短路径
• 对于宽度很大的图，可能效率不高

与其他算法的比较

相比于广度优先搜索(BFS)，DFS使用较少的内存，但BFS能找到最短路径。

8. 应用场景

实际应用

• 检测图中的环
• 拓扑排序
• 寻找强连通分量
• 解决迷宫问题
• 路径查找问题
• 网络爬虫

相关领域

• 图论算法
• 网络分析
• 人工智能中的状态空间搜索
• 编译器设计中的数据流分析

9. 练习与作业

理论题

1. 分析DFS和BFS在不同图结构下的性能差异。
2. 证明DFS可以用于检测无向图中的环。

编程题

1. 实现DFS算法，处理各种边界条件。
2. 使用DFS检测有向图中是否存在环。
3. 实现使用DFS进行拓扑排序。

项目作业

设计一个简单的网络爬虫，使用DFS策略遍历网站链接，并提取相关信息。

10. 扩展阅读

研究论文

• 图遍历算法的优化研究
• 在并行计算中的应用

进阶资料

• 《算法导论》中的图算法章节
• 《图论算法》相关书籍
• Tarjan算法相关资料

相关算法

• 广度优先搜索(BFS)
• Dijkstra算法
• A*搜索算法
• Tarjan强连通分量算法