图论算法基础:DFS 与 BFS
进入图论章节,核心在于掌握两种基本遍历策略:深度优先搜索(DFS)和广度优先搜索(BFS)。理解它们的原理、适用场景以及数据结构支撑,是解决复杂图问题的基石。
DFS:深度优先搜索
DFS 的核心思想是'一条路走到黑'。从起点出发,沿着某条路径一直深入直到叶子节点或无法继续,然后回溯到上一个节点尝试其他分支。从数据结构角度看,DFS 天然对应栈结构(递归调用栈或显式栈)。
空间复杂度通常与搜索深度成正比,即 O(h)。需要注意的是,DFS 并不保证找到最短路径,它更侧重于穷举所有可能性。
经典应用:全排列问题
生成 1 到 n 的全排列是 DFS 的经典入门题。我们需要记录当前已选数字的状态(st 数组),并用 path 数组保存当前路径。当层数达到 n 时,说明已选够 n 个数,输出结果并回溯。
#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("%d ", path[i]);
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);
;
}


