DFS(深度优先搜索)
顾名思义,深度优先搜索,即搜索的一种;
在搜索时,优先向下一深度搜索,可以称作回溯法。
主要实现方法是依靠递归函数;
样例
若使用DFS的搜索方法;
在下图树各点中的遍历方法为:
0 - > 1 - > 3 - > 5 - >3 - > 6 - > 3 - > 1 - > 4 - > 7 - > 9 - > 7 - > 4 - > 1 - > 0 - > 2 - > 8 - >9;
可以看到遍历方法优先增加深度(即 层数)
即能向下一层移动,就先向下一层移动,若没有,则回溯到上一层
可以说是 《长驱直入》,也可以说是一条路走到黑(再回头);
典型的递归(不是吗)
DFS模版
int dfs(int t)
{
if(满足输出条件) //即递归出口
{
输出解; //若有特殊输出格式,用自定义的 void print 函数
}
else
{
for(int i=1;i<=尝试方法数;i++)
if(满足进一步搜索条件)
{
为进一步搜索所需要的状态打上标记;
dfs(t+1);
恢复到打标记前的状态;//也就是说的{回溯一步}
}
}
}
此上为DFS的模版(一般的)可以看出主要依靠不断回溯来找到问题的解;
注意事项:
-
第一个if是符合输出解的条件,第二个
if
是符合进一步搜索的条件; -
下一步搜索时,不是使用
return dfs(t+1)
而是直接dfs(t+1)
(可能会注意不到这个关键的地方,以至于每次写完不知道为什么只得到一个答案就返回主程序了)
-
for
循环之后的if
可以是多个; -
for
循环边界
例题
拿P1706来说
按照字典序输出自然数 1 到 n 所有不重复的排列;
可以看出输出解的条件为当前已选的数的个数为n时,打印解(用print
函数);
否则继续搜索;
代码如下:
后记
不过这种方法也有不足之处
也用此图解释,若解为 $2$ 时,这时遍历左半边树是完全没有必要的;
当然我们也有解决的办法(即广度优先搜索(BFS))
这也就显现出了DFS与BFS的不同和各自的适用范围
DFS: 有多少组解的问题
BFS:最优解问题
标签:输出,优先,DFS,BFS,搜索,深度 From: https://www.cnblogs.com/adsd45666/p/18018764