DFS 算法课堂笔记

一、树的 DFS：计算根节点到各节点距离

问题场景

给定一棵无向树，计算从根节点（如节点 1）到所有其他节点的距离。

核心思路

• 树的存储：使用邻接表 vector<st> e[N]，每个元素存目标节点 to 和边权 jl。
• DFS 遍历：从根节点出发，递归访问子节点，跳过父节点（避免回走），累计距离。

代码结构

struct st { int to, jl; }; // 边：目标节点 to，距离 jl
vector<st> e[N];           // 邻接表存树
int dist[N];               // dist[i]：根到 i 的距离

// u：当前节点，r：父节点（防止回走）
void dfs(int u, int r) {
    for (int i = 0; i < e[u].size(); i++) {
        st bian = e[u][i];
        if (bian.to == r) continue; // 跳过父节点
        dist[bian.to] = dist[u] + bian.jl; // 累计距离
        dfs(bian.to, u); // 递归子节点
    }
}

// 主函数调用
dfs(1, 0); // 根节点 1，父节点设为 0（无父）

关键注意

• 树是无环图，DFS 无需回溯（只需遍历，无需撤销标记）。
• 必须跳过父节点，否则会死循环。

二、网格 DFS：判断起点到终点是否可达

问题场景

在 n×m 网格中，'s' 是起点，'g' 是终点，'#' 是障碍物，判断能否从 s 走到 g。

核心思路

• 方向数组：dx[4], dy[4] 控制上下左右 4 个方向。
• 访问标记：vis[x][y] 标记已走的点，避免重复。
• DFS 流程：从起点出发，递归探索所有合法方向，若到达终点则标记成功。

代码结构

char a[305][305];   // 网格地图
int vis[310][310];  // 访问标记
int dx[5] = {1, 0, 0,-1}; // 方向数组（下、右、左、上）
int dy[5] = {0, 1,-1, 0};
int f = 0;           // 标记是否到达终点

// (x,y)：当前坐标
void dfs(int x, int y) {
    if (x == ex && y == ey) { // 到达终点
        f = 1;
        return;
    }
    // 遍历 4 个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        // 检查：边界内 + 未访问 + 非障碍物
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && 
            vis[nx][ny] == 0 && a[nx][ny] != '#') {
            vis[nx][ny] = 1; // 标记已访问
            dfs(nx, ny);     // 递归探索
        }
    }
}

// 主函数流程
// 1. 输入地图，找起点 sx,sy 和终点 ex,ey
// 2. 标记起点已访问：vis[sx][sy] = 1
// 3. 调用 DFS：dfs(sx, sy)
// 4. 若 f==1 输出 Yes，否则 No

关键注意

• 逻辑统一性：先检查合法性（边界、访问、障碍），再标记和递归。
• 此类连通性问题无需回溯（标记后不撤销，因为只需知道“是否可达”）。

三、DFS 题型小总结