啊哈算法之深度优先搜索(Depth First Search,DFS)
程序员文章站
2022-05-22 20:57:07
...
理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步如何做”则与“当下该如何做”是一样的。比如我们这里写的dfs(step)函数的主要功能就是解决当你在第step个盒子的时候该怎么办。通常的方法就是把每一种可能都去尝试一遍(一般使用for循环来遍历)。当前这一步解决后便进入下一步dfs(step+1).
下面代码就是深度优先搜索的基本模型:
void dfs(int step)
{
判断边界
尝试每一种可能for(i=1;i<=n;i++)
{
继续下一步dfs(step+1);
}
返回;
}
下面这段代码是前面暴力枚举中例题的另一种解法:
#include <stdio.h>
#include <iostream>
int a[10], book[10], n=9, total;
void dfs(int step)
{
int i;
if (step == n + 1)
{
if (a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6] == a[7] * 100 + a[8] * 10 + a[9])
{
total++;
printf("%d%d%d+%d%d%d = %d%d%d\n", a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]);
}
return ;
}
for (i = 1; i <= n; i++)
{
if (book[i] == 0)
{
a[step] = i;
book[i] = 1;
dfs(step + 1);
book[i] = 0;
}
}
//return ;
}
int main()
{
dfs(1);
printf("total = %d\n", total / 2);
system("pause");
return 0;
}
推荐阅读
-
啊哈算法之简单深度优先搜索案例
-
PHP实现深度优先搜索算法(DFS,Depth First Search)详解
-
《算法笔记》—— "迷宫求解" 之 深度优先搜索(DFS)
-
《算法笔记》8.1小节——搜索专题->深度优先搜索(DFS)之[递归入门]全排列
-
数据结构与算法--之DFS 深度优先搜索算法
-
深度优先搜索 DFS(Depath First Search, DFS)
-
DFS——深度优先算法(Depth First Search)
-
DFS——深度优先算法(Depth First Search)
-
深度优先搜索(Depth-First-Search,DFS)
-
啊哈算法之深度优先搜索(Depth First Search,DFS)