深度优先搜索（DFS）——八皇后问题与全排列问题

在这里插入图片描述
（ ^ _ ^ ）
数据结构好难哇（哭

1.BFS和DFS

	数据结构	空间	性质
DFS	stack	O(h)	不具有最短性质
BFS	queue	O(2^h)	具有最短路性质

空间上DFS占优势，但是BFS具有最短性
（若所有权重都是1，则BFS一定最短）（应用：最短距离，最少步数）

2.DFS

深度优先搜索（Depth-First Search, DFS）是算法领域的核心思想之一，它像探险家一样执着地向深处探索，直到触底再回溯寻找新路径。本文将通过八皇后问题和全排列问题两个经典案例，揭开DFS与回溯算法的神秘面纱。

从搜索树的角度来考虑

从两个经典的例子来入手

全排列问题

（P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）


#include <iostream>
using namespace std;const int N = 10;int n;
int path[N];
bool st[N];void dfs(int u) {if (u == n) {for (int i = 0; i < n; i++) {printf("%5d", path[i]);//每个数字5个场宽可以用%5d来实现}puts("");return;}for (int i = 1; i <= n; i++) {if (!st[i]) {path[u] = i;st[i] = true;dfs(u + 1);st[i] = false;}}
}int main() {cin >> n;dfs(0);return 0;
}

八皇后问题

（P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）

冷知识：皇后是米字攻击（不会就我不知道吧orzorz

每一行只会有一个皇后

左下到右上的斜线，同一条上，横纵坐标之和不变，即dg数组的同一格；左上到右下斜线同理，udg数组。

核心逻辑：

*列冲突检测：col not in queens

*主对角线检测：row-col唯一

*副对角线检测：row+col唯一

*递归层级：每层对应一行皇后位置选择

*复杂度分析：时间复杂度O(N!)，空间复杂度O(N)

#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)#include <iostream>
using namespace std;const int N = 20;int n;
int path[N];
bool col[N], dg[N * 2], udg[N * 2];  // 对角线数组大小调整为 2*N
int cnt = 0;  // 记录解的总数// 深度优先搜索函数
void dfs(int u) {if (u == n) {cnt++;if (cnt <= 3) {for (int i = 0; i < n; i++) {if (i > 0) cout << " ";cout << path[i] + 1;  // 输出列号，从 1 开始}cout << endl;}return;}for (int i = 0; i < n; i++) {if (!col[i] && !dg[u + i] && !udg[n - u + i]) {path[u] = i;col[i] = dg[u + i] = udg[n - u + i] = true;dfs(u + 1);col[i] = dg[u + i] = udg[n - u + i] = false;  // 回溯}}
}int main() {cin >> n;dfs(0);cout << cnt << endl;  // 输出解的总数return 0;
}

问题对比与本质解析

特性	八皇后问题	全排列问题
搜索空间	树状结构（每层选择列位置）	排列树（元素选择组合）
约束条件	三维冲突检测（行、列、对角线）	一维约束（元素不可重复使用）
剪枝策略	提前终止非法路径	通过标记数组避免重复选择
解的特征	二维空间布局	一维元素序列
时间复杂度	O(n!)	O(n×n!)