深度优先搜索

深度优先搜索

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);
}