01、深度优先搜索

今天给大家介绍一下深搜和广搜，其实在图基本都讲过了，在这里再深入说一下

什么是图的遍历

基本概念

图的遍历是指从图中的某个顶点出发，访问图中所有顶点，且每个顶点仅被访问一次的过程。

图的两种主要遍历方式：
1. 深度优先搜索（Depth-First Search, DFS）
   - 优先往深处走，走到尽头再回头

2. 广度优先搜索（Breadth-First Search, BFS）
   - 优先访问离起点近的节点，一层层扩散

适用数据结构

DFS 和 BFS 都可以用于：
- 树（Tree）
- 图（Graph）
- 矩阵（Matrix）- 可以看作特殊的图
- 其他连通结构

深度优先搜索（DFS）

核心思想

深度优先搜索（DFS）：一条路走到黑

策略：
1. 从起点出发，选择一个方向
2. 一直往前走，直到走不通
3. 回退到上一个节点，尝试其他方向
4. 重复2-3，直到所有节点都访问过

特点：
- 使用栈（Stack）实现，或用递归（隐式栈）
- 空间复杂度：O(h)，h 是深度
- 适合：路径问题、连通性判断、拓扑排序

给大家一个现实的比喻（不撞南墙不回头）

迷宫探险：

你在迷宫里探险，采用 DFS 策略：
1. 选择一条路一直走
2. 遇到死路就回头
3. 回到岔路口，选择没走过的路
4. 继续一条路走到底

就像走迷宫时，在墙上做标记，
遇到标记过的路就不走了。

这里给大家说一下二叉树的深度优先搜索

树的DFS遍历

树结构：
        1
       / \
      2   3
     / \   \
    4   5   6

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

DFS 遍历过程（递归）：

步骤1: 访问 1
       1 ✓
      / \
     2   3
    / \   \
   4   5   6

步骤2: 往左走，访问 2
       1
      / \
     2✓  3
    / \   \
   4   5   6

步骤3: 继续往左，访问 4
       1
      / \
     2   3
    / \   \
   4✓  5   6

步骤4: 4 没有子节点，回退到 2
       访问 2 的右子节点 5
       1
      / \
     2   3
    / \   \
   4   5✓  6

步骤5: 5 没有子节点，回退到 1
       访问 1 的右子节点 3
       1
      / \
     2   3✓
    / \   \
   4   5   6

步骤6: 访问 3 的右子节点 6
       1
      / \
     2   3
    / \   \
   4   5   6✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

DFS 遍历顺序: 1 → 2 → 4 → 5 → 3 → 6

图的深搜，见这个文章 图

DFS 实现方式

递归实现（推荐）

/**
 * DFS 递归实现（树的遍历）
 */
void dfs(TreeNode* node) {
    // 终止条件
    if (node == nullptr) {
        return;
    }

    // 处理当前节点
    cout << node->val << " ";

    // 递归访问子节点
    dfs(node->left);   // 左子树
    dfs(node->right);  // 右子树
}

DFS 时间与空间复杂度

图的 DFS：
- 时间复杂度：O(V + E)
  V: 顶点数，E: 边数
  每个顶点访问一次，每条边检查一次

- 空间复杂度：O(V)
  递归栈的深度，最坏情况是链状图

树的 DFS：
- 时间复杂度：O(n)
  n 是节点数，每个节点访问一次

- 空间复杂度：O(h)
  h 是树的高度
  平衡树：O(log n)
  退化成链：O(n)