DFS(搜索)
DFS 为图论中的概念,详见 DFS(图论) 页面。在 搜索算法 中,该词常常指利用递归函数方便地实现暴力枚举的算法,与图论中的 DFS 算法有一定相似之处,但并不完全相同。
考虑这个例子:
例题
把正整数
对于这个问题,如果不知道搜索,应该怎么办呢?
当然是三重循环,参考代码如下:
1 2 3 4 | for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
for (int k = j; k <= n; ++k)
if (i + j + k == n) printf("%d=%d+%d+%d\n", n, i, j, k);
|
那如果是分解成四个整数呢?再加一重循环?
那分解成小于等于
这时候就需要用到递归搜索了。
该类搜索算法的特点在于,将要搜索的目标分成若干“层”,每层基于前几层的状态进行决策,直到达到目标状态。
考虑上述问题,即将正整数
设一组方案将正整数
我们将问题分层,第
为了记录方案,我们用 arr 数组,第 i 项表示
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | int m, arr[103]; // arr 用于记录方案
void dfs(int n, int i, int a) {
if (n == 0) {
for (int j = 1; j <= i - 1; ++j) printf("%d ", arr[j]);
printf("\n");
}
if (i <= m) {
for (int j = a; j <= n; ++j) {
arr[i] = j;
dfs(n - j, i + 1, j); // 请仔细思考该行含义。
}
}
}
// 主函数
scanf("%d%d", &n, &m);
dfs(n, 1, 1);
|
例题¶
C++ 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | bool vis[N]; // 访问标记数组
int a[N]; // 排列数组,按顺序储存当前搜索结果
void dfs(int step) {
if (step == n + 1) { // 边界
for (int i = 1; i <= n; i++) {
cout << setw(5) << a[i];
}
cout << endl;
return;
}
for (int i = 1; i <= n; i++) {
if (vis[i] == 0) {
vis[i] = 1;
a[step] = i;
dfs(step + 1);
vis[i] = 0;
}
}
return;
}
|
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用