发布于 ,更新于 

搜索基础

DFS与BFS

深度优先搜索: 一棵树从一个枝向下搜索,搜到头之后回溯,继续搜下一个枝
宽度优先搜索(Breath First Search 而不是 Brain Fuck Scheduler)(后者已经停止维护了): 一层一层搜到底部

DFS

注意回溯需要“恢复现场”

一个例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>

const int N = 10;

int n; // 层数
int path[N]; // 存储状态
bool state[N]; // 存储各个枝是否被使用

void dfs(int a) {
if (a == n) { // 到达最底层
for (int i = 0; i < n; i ++) {
printf("%5d",path[i]);
}
putchar('\n');
return ;
}

for (int i = 1; i <= n; i ++) {
if (!state[i]) { // i没有被使用
path[a] = i;
state[i] = 1;
dfs(a+1); // 搜索下一层
state[i] = 0; // dfs结束之后,开始回溯,恢复现场
}
}
}

int main() {
scanf("%d",&n);

dfs(0);

return 0;
}