目录
一、回溯法与深度优先搜索（DFS）
二、DFS与二叉树的前序遍历
2.1、二叉树的前序遍历
2.2、DFS
全排列
2.3、分析
三、N皇后问题
一、回溯法与深度优先搜索（DFS）
1. 回溯法：
- 是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解的话（或者至少不是最后一个解），回溯法会通过在上一步进行一些变化来摆脱当前不正确的解，重新尝试其他的可能性。
- 它通常用于解决决策问题，如排列、组合、子集等。
- 回溯法可以隐式地处理图或树，即这些结构并不需要事先构建出来，而是在搜索过程中动态生成。
2. 深度优先搜索（DFS）：
- 是一种用于遍历或搜索树或图的算法。在树中，这种算法搜索最深的节点，而在图中，它将回溯到未探索过的路径。
- DFS从根（或在图中的某个任意节点）开始，探索尽可能深的分支，直到达到目标节点，或者当前分支没有更多的节点可以访问。然后，搜索回溯到开始探索的路径上的下一个节点。
- DFS通常使用栈或递归来实现，其中递归实现更为常见和直观。
关系：
- 回溯法通常使用DFS作为其基本的搜索策略。在回溯法中，DFS用于系统地遍历所有可能的解空间。
- 当我们说“一条路走到黑”时，我们实际上是在描述DFS的特性，即尽可能深入地搜索图的分支，直到达到叶节点或无法继续为止。
- 在排列型问题中，DFS用于生成所有可能的排列，而在子集型问题中，它用于生成所有可能的子集。
尽管在很多情况下回溯法和DFS是紧密相关的，但它们并不总是等价的。回溯法更侧重于问题的求解策略，而DFS更侧重于图的遍历策略。然而，在实际应用中，这两个概念经常交织在一起。
二、DFS与二叉树的前序遍历
2.1、二叉树的前序遍历
前序遍历的步骤如下：
// 先序遍历二叉树
void PrevOrder(BTNode* root)
{
// 如果当前节点为空，则打印"NULL"并返回
if (root == NULL)
{
printf("NULL ");
return;
}
// 访问当前节点的数据
printf("%c ", root->data);
// 递归遍历左子树
PrevOrder(root->left);
// 递归遍历右子树
PrevOrder(root->right);
}2.2、DFS
基本模型：
void dfs(int step){
判断边界
枚举每一种可能 for(i=1;i<=n;i++){
继续下一步 dfs(step+1)
}
}
全排列
题目：
输入一个数n，将数字1~n排成一排，按字典序输出所有排列方法。
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int ans[N];
bool mark[N];// 标记是否走过
int n;
void dfs(int u) // u代表目前dfs深度
{
if (u == n)// 判断边界， 找到解
{
for (int i = 0; i < n; i++)
cout << ans[i] << " ";
// 打印当前排列
cout << '\n';
return;
}
for (int i = 1; i <= n; i++)// 枚举下一种情况
{
if (mark[i] == false)
// 尝试将每个未使用的数字放入当前位置
{
mark[i] = true;// 标记已用
ans[u] = i;// 数字i放入当前深度u的位置
dfs(u + 1);// 递归调用dfs函数，处理下一个深度
mark[i] = false;
ans[u] = 0;
}
}
}
int main()
{
cin >> n;dfs(0);//从0开始调用dfs函数生成排列
return 0;
}这是一个排列型搜索树，实际上的回溯法比较灵活，需要根据题意要求来具体分析。vis[i]表示数字i是否使用过，也经常被用于表示某个元素是否使用过al]存放结果，当dep深度=n+1时说明n层都已经算完了，直接输出结果。子集型搜索树模板结构类似，就是在往下走的时候只有两条边，表示“选或不选当前这个元素”
2.3、分析
二叉树的前序遍历确实与深度优先遍历（DFS）在原理上是相似的。前序遍历是二叉树深度优先遍历的一种形式。
- 前序遍历顺序：在二叉树的前序遍历中，我们首先访问当前节点（根节点或任意子树的根），然后递归地前序遍历左子树，最后递归地前序遍历右子树。这个“根-左-右”的顺序确保了遍历是深度优先的。
- 深度优先遍历：深度优先遍历是一种树或图遍历算法，它从根节点（或任意节点）开始，尽可能深地探索图的分支。在树中，这意味着沿着树的最深路径进行搜索，直到到达叶节点或无法再深入，然后回溯到开始搜索的路径上的下一个节点。
在二叉树的前序遍历中，每个节点被访问的顺序实际上反映了DFS搜索树的方式。先访问当前节点对应于DFS中的“探索当前节点”，然后深入左子树对应于“先探索最左边的分支”，最后访问右子树则是“在左侧无更多可探索路径时，回溯并探索右侧的分支”。
因此，我们可以说，二叉树的前序遍历是一种特殊形式的深度优先遍历，其中特定的节点访问顺序（根-左-右）体现了DFS的基本原则。两者都是基于深度优先搜索的概念来遍历结构的。
三、N皇后问题
题目描述：
在一个 N x N 的方格棋盘上放置 N 个皇后，要求它们互不攻击，即任意两个皇后不允许处在同一行、同一列，也不允许处在与棋盘边框成 45 度角的斜线上。给定一个正整数 N（N < 10），你的任务是求出在这样的棋盘上放置 N 个皇后的合法方法有多少种。
输入描述：
输入包含一个正整数 N（N <= 10），表示棋盘的大小和需要放置的皇后的数量。
输出描述：
输出一个正整数，表示在给定大小的棋盘上放置 N 个皇后的合法方法数量。
输入：5
输出：10
思路：对于这种题，首先，我们想到的是使用二维数组存，然后暴力枚举，判断函数来一个一个判断。那么，就得到了一个大概的思路：对二维数组的所有情况进行枚举，然后对每种情况进行判断，这是这种题目的普遍思想，接下来是对题目进行细致的分析。
这种题主要的难点是判断、遍历如何实现。由题意可知，一行，一列中最多有一个皇后存在，所以可以把一行或一列看成一组，这里我们把一行看成一组。因为第一行是没有放过任何皇后的，所以第一行全部都枚举放置皇后，接下来的每行，我们可以设置一个check函数来检查是否可以放置皇后，这时，就构成了我们代码的完整思路。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int a[11][11];
// 存储棋盘的数组，1表示为皇后，0表示为空
int ans = 0; int n;
// 解的数量， 棋盘的大小，即N
// 判断是否有攻击
bool check(int deep, int m) {
for (int k = 0; k < n; ++k) {
if (a[k][m]) return false;
// 检查第 m 列是否有皇后
}
// 检查所有方向以判断皇后是否会攻击
//下方还没有放置皇后，所以不用检查
for (int i = 1; i <= deep; i++) {
if (a[deep - i][m]) return false; // 检查上方
if (m - i >= 0 && a[deep - i][m - i]) return false; // 检查左上方
if (m + i < n && a[deep - i][m + i]) return false; // 检查右上方
}
return true;
}
void dfs(int deep) {
if (deep == n) {
ans++;// 找到一个解，解的数量加一
return;
}
for (int i = 0; i < n; ++i) {
// 尝试在当前行的每一列放置皇后
if (check(deep, i)) {
a[deep][i] = 1; // 放置皇后
dfs(deep + 1);// 递归搜索下一行
a[deep][i] = 0; // 回溯，移除皇后
}
}
}
int main() {
cin >> n;dfs(0);// 从第0行开始深度优先搜索
cout << ans;
return 0;
}四、2N皇后问题
问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1样例输出
0
此题为N皇后问题的进阶版，相较于N皇后问题需多考虑一组棋子，并且要考虑是否能放入。我们可以先放入黑皇后，再放入白皇后的思路去实现代码。此时要建立dfsblack和dfswhite两个函数。
#include<bits/stdc++.h>
using namespace std;
int a[10][10],
b[10][10],// 存储黑皇后的位置
c[10][10];// 存储白皇后的位置
bool vis[10][10];
int n;// 棋盘大小
int ans;// 几种方法// 判断是否有攻击
bool checkblack(int deep, int m) {
// 检查所有方向以判断皇后是否会攻击
//下方还没有放置皇后，所以不用检查
for (int i = 0; i <= deep; i++) {
if (b[deep - i][m]) return false; // 检查上方
if (m - i >= 0 && b[deep - i][m - i]) return false; // 检查左上方
if (m + i < n && b[deep - i][m + i]) return false; // 检查右上方
}
return true;
}bool checkwhite(int deep, int m) {
// 检查所有方向以判断皇后是否会攻击
//下方还没有放置皇后，所以不用检查
for (int i = 0; i <= deep; i++) {
if (c[deep - i][m]) return false; // 检查上方
if (m - i >= 0 && c[deep - i][m - i]) return false; // 检查左上方
if (m + i < n && c[deep - i][m + i]) return false; // 检查右上方
}
return true;
}dfsblack
放完黑皇后的终止条件为：
if (deep == n) {
dfswhite(0);// 找到一个解，解的数量加一
return;
}
然后判断的条件也增加为
if (checkblack(deep, i) && a[deep][i] != 0) （0不能放置）
void dfsblack(int deep) {
if (deep == n) {
dfswhite(0);// 找到一个解，解的数量加一
return;
}
for (int i = 0; i < n; ++i) {
// 尝试在当前行的每一列放置皇后
if (checkblack(deep, i) && a[deep][i] != 0) {
b[deep][i] = 1; // 放置皇后
vis[deep][i] = true;
dfsblack(deep + 1);// 递归搜索下一行
b[deep][i] = 0; // 回溯，移除皇后
vis[deep][i] = false;
}
}
}dfswhite
检查白皇后是否能放的条件为：
checkwhite(deep, i) && a[deep][i] != 0 && b[deep][i] == 0 （0不能放置，黑放过不能放）
void dfswhite(int deep) {
if (deep == n) {
ans++;// 找到一个解，解的数量加一
return;
}
for (int i = 0; i < n; ++i) {
// 尝试在当前行的每一列放置皇后
if (checkwhite(deep, i) && a[deep][i] != 0 && b[deep][i] == 0) {
c[deep][i] = 1; // 放置皇后
vis[deep][i] = true;
dfswhite(deep + 1);// 递归搜索下一行
c[deep][i] = 0; // 回溯，移除皇后
vis[deep][i] = false;
}
}
}int main() {
cin >> n;
memset(vis, false, sizeof(vis));
memset(c, 0, sizeof(c));
memset(b, 0, sizeof(b));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cin >> a[i][j];
}
dfsblack(0);// 从第0行开始深度优先搜索
cout << ans;
return 0;
}今天就先到这了！！！
看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！文章来源：https://www.toymoban.com/news/detail-841979.html
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。文章来源地址https://www.toymoban.com/news/detail-841979.html
到了这里，关于DFS（深度优先遍历、N皇后问题、2N皇后问题）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
