深度优先搜索

DFS（Depth First Search）中文常叫“深搜”。它的特点是：先沿着一条路走到底，走不动就回退，再换一条路继续走。
DFS 特别适合解决：连通块、找路径、枚举方案、回溯、判环等问题。

---

1. DFS 的核心思想

• 把“当前状态”当作一个点
• 从当前点出发，尝试走到下一个点
• 走过的点要标记（避免无限循环）
• 走到不能走时回退（这就是回溯）

---

2. DFS 常用模板

2.1 图上的 DFS（邻接表）

void dfs(int u){
    vis[u]=1;                 // 1) 标记 u 已访问
    for(int v:adj[u]){        // 2) 枚举 u 的所有邻居 v
        if(!vis[v]) dfs(v);   // 3) 没访问过才递归
    }
}

2.2 网格迷宫 DFS（上下左右）

int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

void dfs(int x,int y){
    vis[x][y]=1;                         // 标记访问
    for(int k=0;k<4;k++){
        int nx=x+dx[k], ny=y+dy[k];
        if(nx<1||nx>n||ny<1||ny>m) continue;  // 边界
        if(vis[nx][ny]) continue;            // 已访问
        if(g[nx][ny]=='#') continue;         // 墙不能走
        dfs(nx,ny);
    }
}

---

3. 连通块

3.1 图上连通块

图上连通块：在图中用 DFS 给可达点标记，统计连通块数量、大小等。

做法：

1. 遍历所有点
2. 如果某点没访问过，说明发现一个新连通块
3. cnt++，从它 DFS，把整块点都标记掉

void dfs(int u){
    vis[u]=1;
    for(int v:adj[u]) if(!vis[v]) dfs(v);
}

int cnt=0;
for(int u=1;u<=n;u++){
    if(!vis[u]){
        cnt++;
        dfs(u);
    }
}

如果要统计每块大小，在 dfs 里加 size++：

void dfs(int u){
    vis[u]=1;
    size++;
    for(int v:adj[u]) if(!vis[v]) dfs(v);
}

---

3.2 迷宫连通块

迷宫连通块：把迷宫看成网格图，用 DFS 统计相连的空地区域数目。

int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

void dfs(int x,int y){
    vis[x][y]=1;
    for(int k=0;k<4;k++){
        int nx=x+dx[k], ny=y+dy[k];
        if(nx<1||nx>n||ny<1||ny>m) continue;
        if(vis[nx][ny]) continue;
        if(g[nx][ny]=='#') continue;
        dfs(nx,ny);
    }
}

int cnt=0;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(g[i][j]=='.' && !vis[i][j]){
            cnt++;
            dfs(i,j);
        }
    }
}

---

4. 判环

4.1 无向图判环

结论： DFS 时遇到已访问但不是父亲的结点 $\Rightarrow$ 有环。

bool hasCycle=false;

void dfs(int u,int fa){
    vis[u]=1;
    for(int v:adj[u]){
        if(!vis[v]){
            dfs(v,u);
        }else if(v!=fa){
            hasCycle=true;
        }
    }
}

---

4.2 有向图判环

三色标记：

• 0：未访问
• 1：正在访问（在递归栈里）
• 2：已访问完成

DFS 中如果走到 state[v]==1，说明回到了递归栈中的点，有环。

bool hasCycle=false;

void dfs(int u){
    state[u]=1;
    for(int v:adj[u]){
        if(state[v]==0) dfs(v);
        else if(state[v]==1) hasCycle=true;
    }
    state[u]=2;
}

---

5. 搜索

5.1 图上搜索（是否存在路径）

从 s DFS，能访问到 t 说明存在路径。

void dfs(int u){
    vis[u]=1;
    for(int v:adj[u]) if(!vis[v]) dfs(v);
}
// dfs(s) 后判断 vis[t]

---

5.2 迷宫搜索（能否到达终点）

void dfs(int x,int y){
    vis[x][y]=1;
    for(int k=0;k<4;k++){
        int nx=x+dx[k], ny=y+dy[k];
        if(nx<1||nx>n||ny<1||ny>m) continue;
        if(vis[nx][ny]) continue;
        if(g[nx][ny]=='#') continue;
        dfs(nx,ny);
    }
}
// dfs(sx,sy) 后判断 vis[tx][ty]

---

5.3 带回溯搜索（枚举方案）

特点： 每层做选择，做完选择后递归，回来要撤销选择。

void dfs(int step){
    if(step==n){
        check();
        return;
    }

    for(each choice){
        do_choice();
        dfs(step+1);
        undo_choice();
    }
}

---

6. 折半搜索（Meet in the middle）

把一次大搜索拆成“前一半 + 后一半”两部分：

• 先 DFS 枚举前一半并存表
• 再 DFS 枚举后一半，用前半结果快速配对
• 常用于子集和等状态数较大的枚举题

dfs1(pos,end,sum){
    if(pos==end){ store(sum); return; }
    dfs1(pos+1,end,sum)
    dfs1(pos+1,end,sum+a[pos]);


dfs2(pos,end,sum){
    if(pos==end){
        if(exist(target-sum)) ok=true;
        return;
    }
    dfs2(pos+1,end,sum);
    dfs2(pos+1,end,su
}

---

7. 暴力枚举

把“枚举所有方案”的过程写成 DFS：

• 每一层代表一次决策
• 到达叶子结点就得到一个完整方案并检查是否满足条件
• 可配合剪枝提前丢掉不可能分支

void dfs(int i){
    if(i==n){
        check();
        return;
    }

    // 例：每个位置选 0 或 1
    choose0();
    dfs(i+1);

    choose1();
    dfs(i+1);
}

【前置知识点】
1、基础数据结构
2、递归

【后置衔接知识点】
1、最近公共祖先

【思维导图】

【题目知识点分类】