DFS（深度优先遍历）
一、回溯法与深度优先搜索（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;
}今天就先到这了！！！