一、定义DFS 是一种用于遍历或搜索树/图的算法。核心思想是“一条路走到黑撞了南墙就回头”。二、相关概念回溯走不通就回头恢复原来的样子继续尝试别的可能。剪枝提前发现这条路行不通直接不走了节省时间。 砍掉无效分支三、核心原理DFS的工作流程本质是利用“栈”的数据结构先进后出来记录访问路径确保我们能“回溯”到上一个节点。这里要注意两个点访问与回溯的逻辑从起始节点出发标记该节点为“已访问”避免重复访问陷入死循环选择该节点的一个未访问邻居节点继续深入访问递归/栈推进当某个节点没有未访问的邻居时说明这条路走到头了回溯到上一个节点继续寻找其他未访问的邻居重复步骤2-3直到所有节点都被访问完毕。隐式栈 vs 显式栈很多人第一次学DFS会困惑“栈在哪里”——其实有两种实现方式对应两种栈隐式栈用递归实现时系统会自动创建“调用栈”递归的每一层就是栈的一个元素回溯就是栈的弹出操作递归返回显式栈用迭代实现时我们自己定义一个栈结构手动将节点压入、弹出模拟递归的过程。本篇博客先使用递归实现递归写法的三要素终止条件什么时候算找到答案了什么时候是死路越界、已访问当前层操作标记已访问visited、记录路径。下潜与回溯进入下一层递归回来后撤销操作状态重置。四、例题排列数字题目描述题目来源于AcWing思路使用path数组存储每次的路径。visited数组存储该数组是否被访问过。对于1~n的数进行深度优先搜索。判断当前是否已经填完了全部的数如果是则直接数组path对于每个数判断当前数是否已经被填过了。如果没有被填过则把当前数加入在path中同时把该数的状态设置为已经被访问。进入下一个要填数的位置重复步骤12。如果该条路径到底就回溯。若该数被填过了则判断下一个数是否被填过。代码#includeiostream using namespace std; const int N 10; int n; //path数组用于存储每次排列的组合,visited数组用于存储当前数字是否被填过 int path[N]; bool visited[N]; //深度优先搜索---u表示当前正在填第几个数 void dfs(int u){ //如果已经填完了所有数---输出该组合 if(u n){ for(int i 0; i n; i){ coutpath[i] ; } //每种组合换行 coutendl; } //对于每个数需要判断当前的数有没有填过 for(int i 0; i n; i){ if(visited[i] false){ //如果当前的数没有访问过--则把当前数字填入path中同时设置该数字已经被访问过 path[u] i 1; visited[i] true; //走到下一个要填的位置 dfs(u 1); //恢复为未访问 visited[i] false; } } } int main(){ cinn; //调用dfs函数 dfs(0); return 0; }n皇后问题题目描述题目来源于AcWing方法一一行放一个皇后dfs按行递归思路一行放一个皇后用 DFS 按行递归放之前检查列、对角线是否冲突不冲突就放皇后 标记占用递归到下一行回溯撤销标记继续尝试其他列放完 n 行 →输出方案代码#includeiostream using namespace std; const int N 10; int n; //row存储每行是否出现皇后col存储列dg存储对角线udg存储反对角线 int row[N], col[N], dg[2 * N], udg[2 * N]; //path存储当前方案 char path[N][N]; //u表示当前放皇后的行数 void dfs(int u){ //判断是否把皇后都放完了 if(u n){ //输出方案 for(int i 0; i n; i){ coutpath[i]endl; } coutendl; } //遍历每一列 for(int i 0; i n; i){ //如果满足行列对角线反对角线都没有放皇后---则可以放 if(!col[i] !dg[u i] !udg[n - u i]){ path[u][i] Q; //同时设置该行列对角线反对角线都已经放了皇后 col[i] dg[u i] udg[n - u i] true; //进入下一个位置 dfs(u 1); //回溯时修改状态 col[i] dg[u i] udg[n - u i] false; path[u][i] .; } } } int main(){ cinn; //输出化棋盘全为. for(int i 0; i n; i){ for(int j 0; j n; j){ path[i][j] .; } } //调用深度优先搜索函数 dfs(0); return 0; }方法二遍历每一个格子:每个格子有放和不放两种状态思路一个格子一个格子遍历每个格子只有两种选择不放皇后 或 放皇后。先试 “不放”走不通再回头试 “放”放满 n 个就输出答案。从 (0,0) 开始一格一格走每个格子先不放 → 去下一格回来后 → 能放就放放皇后必须满足行列斜线都没皇后放满 n 个 → 输出方案走不通 → 回溯撤销操作直到搜索完所有可能代码#includeiostream using namespace std; const int N 10; int n; //row存储每行是否出现皇后col存储列dg存储对角线udg存储反对角线 int row[N], col[N], dg[2 * N], udg[2 * N]; //path存储当前方案 char path[N][N]; //x表示当前行数y表示列数s表述皇后的总数 void dfs(int x, int y, int s){ //如果皇后大于需要的数直接结束 if(s n){ return ; } //如果格子走到越界则切换到下一行 if(y n){ y 0; x; } //走到最后一行时判断 if(x n){ //判断是否把皇后都放完了 if(s n){ //输出方案 for(int i 0; i n; i){ coutpath[i]endl; } coutendl; } return; } //没有放皇后就是.进入下一个格子 path[x][y] .; dfs(x, y 1, s); //判断是否满足条件 if(!row[x] !col[y] !dg[x y] !udg[x - y n]){ path[x][y] Q; //同时设置该行列对角线反对角线都已经放了皇后 row[x] col[y] dg[x y] udg[x - y n] true; //进入下一个位置 dfs(x,y 1,s 1); //回溯时修改状态 row[x] col[y] dg[x y] udg[x - y n] false; path[x][y] .; } } int main(){ cinn; //输出化棋盘全为. for(int i 0; i n; i){ for(int j 0; j n; j){ path[i][j] .; } } //调用深度优先搜索函数 dfs(0,0,0); return 0; }
【搜索与图论】DFS算法（深度优先搜索）
一、定义DFS 是一种用于遍历或搜索树/图的算法。核心思想是“一条路走到黑撞了南墙就回头”。二、相关概念回溯走不通就回头恢复原来的样子继续尝试别的可能。剪枝提前发现这条路行不通直接不走了节省时间。 砍掉无效分支三、核心原理DFS的工作流程本质是利用“栈”的数据结构先进后出来记录访问路径确保我们能“回溯”到上一个节点。这里要注意两个点访问与回溯的逻辑从起始节点出发标记该节点为“已访问”避免重复访问陷入死循环选择该节点的一个未访问邻居节点继续深入访问递归/栈推进当某个节点没有未访问的邻居时说明这条路走到头了回溯到上一个节点继续寻找其他未访问的邻居重复步骤2-3直到所有节点都被访问完毕。隐式栈 vs 显式栈很多人第一次学DFS会困惑“栈在哪里”——其实有两种实现方式对应两种栈隐式栈用递归实现时系统会自动创建“调用栈”递归的每一层就是栈的一个元素回溯就是栈的弹出操作递归返回显式栈用迭代实现时我们自己定义一个栈结构手动将节点压入、弹出模拟递归的过程。本篇博客先使用递归实现递归写法的三要素终止条件什么时候算找到答案了什么时候是死路越界、已访问当前层操作标记已访问visited、记录路径。下潜与回溯进入下一层递归回来后撤销操作状态重置。四、例题排列数字题目描述题目来源于AcWing思路使用path数组存储每次的路径。visited数组存储该数组是否被访问过。对于1~n的数进行深度优先搜索。判断当前是否已经填完了全部的数如果是则直接数组path对于每个数判断当前数是否已经被填过了。如果没有被填过则把当前数加入在path中同时把该数的状态设置为已经被访问。进入下一个要填数的位置重复步骤12。如果该条路径到底就回溯。若该数被填过了则判断下一个数是否被填过。代码#includeiostream using namespace std; const int N 10; int n; //path数组用于存储每次排列的组合,visited数组用于存储当前数字是否被填过 int path[N]; bool visited[N]; //深度优先搜索---u表示当前正在填第几个数 void dfs(int u){ //如果已经填完了所有数---输出该组合 if(u n){ for(int i 0; i n; i){ coutpath[i] ; } //每种组合换行 coutendl; } //对于每个数需要判断当前的数有没有填过 for(int i 0; i n; i){ if(visited[i] false){ //如果当前的数没有访问过--则把当前数字填入path中同时设置该数字已经被访问过 path[u] i 1; visited[i] true; //走到下一个要填的位置 dfs(u 1); //恢复为未访问 visited[i] false; } } } int main(){ cinn; //调用dfs函数 dfs(0); return 0; }n皇后问题题目描述题目来源于AcWing方法一一行放一个皇后dfs按行递归思路一行放一个皇后用 DFS 按行递归放之前检查列、对角线是否冲突不冲突就放皇后 标记占用递归到下一行回溯撤销标记继续尝试其他列放完 n 行 →输出方案代码#includeiostream using namespace std; const int N 10; int n; //row存储每行是否出现皇后col存储列dg存储对角线udg存储反对角线 int row[N], col[N], dg[2 * N], udg[2 * N]; //path存储当前方案 char path[N][N]; //u表示当前放皇后的行数 void dfs(int u){ //判断是否把皇后都放完了 if(u n){ //输出方案 for(int i 0; i n; i){ coutpath[i]endl; } coutendl; } //遍历每一列 for(int i 0; i n; i){ //如果满足行列对角线反对角线都没有放皇后---则可以放 if(!col[i] !dg[u i] !udg[n - u i]){ path[u][i] Q; //同时设置该行列对角线反对角线都已经放了皇后 col[i] dg[u i] udg[n - u i] true; //进入下一个位置 dfs(u 1); //回溯时修改状态 col[i] dg[u i] udg[n - u i] false; path[u][i] .; } } } int main(){ cinn; //输出化棋盘全为. for(int i 0; i n; i){ for(int j 0; j n; j){ path[i][j] .; } } //调用深度优先搜索函数 dfs(0); return 0; }方法二遍历每一个格子:每个格子有放和不放两种状态思路一个格子一个格子遍历每个格子只有两种选择不放皇后 或 放皇后。先试 “不放”走不通再回头试 “放”放满 n 个就输出答案。从 (0,0) 开始一格一格走每个格子先不放 → 去下一格回来后 → 能放就放放皇后必须满足行列斜线都没皇后放满 n 个 → 输出方案走不通 → 回溯撤销操作直到搜索完所有可能代码#includeiostream using namespace std; const int N 10; int n; //row存储每行是否出现皇后col存储列dg存储对角线udg存储反对角线 int row[N], col[N], dg[2 * N], udg[2 * N]; //path存储当前方案 char path[N][N]; //x表示当前行数y表示列数s表述皇后的总数 void dfs(int x, int y, int s){ //如果皇后大于需要的数直接结束 if(s n){ return ; } //如果格子走到越界则切换到下一行 if(y n){ y 0; x; } //走到最后一行时判断 if(x n){ //判断是否把皇后都放完了 if(s n){ //输出方案 for(int i 0; i n; i){ coutpath[i]endl; } coutendl; } return; } //没有放皇后就是.进入下一个格子 path[x][y] .; dfs(x, y 1, s); //判断是否满足条件 if(!row[x] !col[y] !dg[x y] !udg[x - y n]){ path[x][y] Q; //同时设置该行列对角线反对角线都已经放了皇后 row[x] col[y] dg[x y] udg[x - y n] true; //进入下一个位置 dfs(x,y 1,s 1); //回溯时修改状态 row[x] col[y] dg[x y] udg[x - y n] false; path[x][y] .; } } int main(){ cinn; //输出化棋盘全为. for(int i 0; i n; i){ for(int j 0; j n; j){ path[i][j] .; } } //调用深度优先搜索函数 dfs(0,0,0); return 0; }
