图论核心：深度搜索DFS 与广度搜索BFS _dfs 优先队列
一、深度优先搜索（DFS）：一条路走到黑的探索哲学
1. 算法核心思想
DFS（Depth-First Search）遵循 “深度优先” 原则，从起始节点出发，尽可能深入地访问每个分支，直到无法继续时回溯，尝试其他路径。这种策略类似走迷宫时 “不撞南墙不回头” 的探索方式，通过递归或栈结构实现路径的遍历与回溯。
2. 经典场景：全排列问题（字典序输出）
问题描述：给定整数 n，按字典序输出 1~n 的所有排列。
算法分析：
- 用
ans数组记录当前排列，mark数组标记数字是否已使用。 - 递归函数
dfs(u)表示填充第 u 位数字，通过枚举 1~n 的未使用数字，递归构建全排列。 - 回溯时需清除标记，确保数字可重复选择（不同排列路径）。
C++ 代码实现：
cpp
#include using namespace std;const int N = 10;int ans[N], n;bool mark[N]; // 标记数字是否已使用void dfs(int u) { if (u == n) { // 递归终止条件：填满所有位置 for (int i = 0; i < n; i++) cout << ans[i]; cout << endl; return; } for (int i = 1; i > n; dfs(0); return 0;}3. 算法特性与应用
- 空间效率：递归深度为图的高度，最坏情况下需 O (n) 空间（如树退化为链表）。
- 典型应用：
- 拓扑排序（有向无环图 DAG）
- 连通分量检测（无向图）
- 路径搜索与环检测
二、广度优先搜索（BFS）：层次扩展的最短路径探索
1. 算法核心思想
BFS（Breadth-First Search）以 “层” 为单位遍历图，从起始节点出发，先访问所有相邻节点（第一层），再依次访问下一层节点。这种策略确保首次访问某节点时路径最短，因此天然适用于最短路径问题。
2. 经典场景：迷宫最短路径
问题描述：在 n×m 的迷宫中，从左上角 (0,0) 到右下角 (n-1,m-1)，求最少移动次数（0 可走，1 为墙）。
算法分析：
- 使用队列实现层次遍历，
mark数组记录到达各点的步数（初始为 - 1 表示未访问）。 - 方向向量
dx/dy定义上下左右移动，每次从队列取出当前节点，向四个方向扩展新节点。 - 首次到达终点时的步数即为最短路径（BFS 的层次特性保证）。
C++ 代码实现：
cpp
#include #include #include using namespace std;typedef pair PII; // 坐标对const int N = 110;int map[N][N], mark[N][N]; // map存储迷宫，mark存储步数int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 上下左右方向int n, m;void bfs() { memset(mark, -1, sizeof mark); // 初始化步数为-1 queue q; q.push({0, 0}); // 起点入队 mark[0][0] = 0; // 起点步数为0 while (!q.empty()) { PII top = q.front(); // 取出当前节点 q.pop(); for (int i = 0; i = 0 && nx = 0 && ny > n >> m; for (int i = 0; i < n; i++) for (int j = 0; j > map[i][j]; bfs(); cout << mark[n-1][m-1] << endl; // 输出最短步数 return 0;}3. 关键细节解析
- 队列的作用：保证按层遍历，先入队的节点先处理，确保首次访问即最短路径。
- 方向向量：通过数组统一管理移动方向，避免重复编写坐标变换代码。
- 标记数组的双重功能：既记录是否访问过，又存储最短步数，空间效率更高。
三、DFS 与 BFS 对比与选型建议
选型建议：
- 求路径存在性或枚举所有可能：优先选 DFS（代码简洁，递归实现更直观）。
- 求最短路径或层次相关问题：必须选 BFS（利用队列的层次特性）。
四、扩展与优化技巧
1. DFS 优化
- 迭代实现：用栈模拟递归，避免系统栈溢出（适用于 n>1e4 的场景）。
- 剪枝策略：提前排除不可能的路径（如全排列中数字已使用），减少递归次数。
2. BFS 优化
- 双向 BFS：从起点和终点同时搜索，相遇时即为最短路径，时间复杂度显著降低。
- 优先队列（Dijkstra 算法）：处理带权图的最短路径问题，本质是 BFS 的贪心扩展。
五、总结
DFS 与 BFS 是图论的基石算法，分别代表 “深度探索” 与 “层次扩展” 的思维模式。掌握两者的核心原理、代码实现及适用场景，是解决图论问题的关键。实际应用中，可根据问题特性灵活选择算法，并结合优化技巧提升效率。
