深度优先搜索的思路和树的先序遍历很像，下面是百度百科上的定义：
深度优先遍历图的方法是，从图中某顶点v出发：
（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发，对图进深度优先遍历；直至图中和v有路径相通的顶点都被访问；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法，那就是广度优先搜索(BFS).
对于定义的理解，可以结合斐波那契数列（虽然用递归来写斐波那契是一种很糟糕的写法）来进行理解，如下图：
其中，右边这个树上的顺序是这样的：
可以结合遍历的思想来理解DFS；
DFS的题目大致可以分为两类：
1，对图的连通性进行检验：如迷宫问题，图的条件搜索。
2，DFS搜索顺序和规则问题，通过你穷举所有答案，找出符合条件的解。即爆搜问题。
看到这里，你可能会有些疑惑具体是怎样的问题，本文就针对DFS的原理进行，常见的题型进行了总结，附上代码和解题思路。
在测试连通性是，DFS的思路是与人们的思想是一致的，在一条路上，我是否可以在这条路上一直走下去，如果走不通，那我就返回原来的节点，换个方向，再沿着一条路走下去，直到成功。
针对连通性问题，我们还可以再进行分类 ：
在这种问题，只需要在每一步中，将搜索到的节点抛弃掉，对于当前搜索到的节点进行计数，最终统计所有能到达的点。
下面给出两个例题：
例1，红与黑(简单)
/*
* @Author: your name
* @Date: 2022-02-11 13:39:15
* @LastEditTime: 2022-02-11 13:56:51
* @LastEditors: Please set LastEditors
* @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
* @FilePath: \All code\26.cpp
*/
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int W, H;
int ans;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
void init()
{
for (int i = 0; i < MAXN; i++)
{
for (int j = 0; j < MAXN; j++)
{
vis[i][j] = false;
}
}
ans = 1;//由于在初始点位置，所以一开始就是一块黑砖
}
void dfs(int x, int y)//常用DFS套路
{
for (int i = 0; i < 4; i++)
{
int newx = x + dx[i];
int newy = y + dy[i];
if (newx >= 1 && newx <= H && newy >= 1 && newy <= W && mp[newx][newy] == '.' && vis[newx][newy] == false)
{
ans++;
vis[newx][newy] = true;
dfs(newx, newy);
}
}
}
int beginx, beginy;
int main()
{
while (1)
{
cin >> W >> H;
if (W == 0 && H == 0)
{
break;
}
init();
for (int i = 1; i <= H; i++)
for (int j = 1; j <= W; j++)
{
cin >> mp[i][j];
if (mp[i][j] == '@')
{
beginx = i;
beginy = j;
}
}
dfs(beginx, beginy);
cout << ans << endl;
}
return 0;
}/*
* @Author: your name
* @Date: 2022-01-22 21:06:31
* @LastEditTime: 2022-01-22 21:32:59
* @LastEditors: Please set LastEditors
* @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
* @FilePath: \All code\9.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN 105
bool vis[MAXN][MAXN];
char mp[MAXN][MAXN];
int row,cow;
int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
void dfs(int x,int y)
{
vis[x][y] = 1;
for(int i =0;i<8;i++)
{
int newx = x+dx[i];
int newy = y+dy[i];
if(newx>=0&&newy>=0&&newx<row&&newy<cow&&mp[newx][newy] == 'W'&&vis[newx][newy] ==0)
{
dfs(newx,newy);
}
}
}
int main()
{
int i, j;
int count =0;
cin >> row >> cow;
for (i = 0; i < row; i++)
for (j = 0; j < cow; j++)
{
cin >> mp[i][j];
}
for (i = 0; i < row; i++)
for (j = 0; j < cow; j++)
{
if(mp[i][j] == 'W'&&vis[i][j] == 0)//碰到一个后，就最这个区域进行DFS，并进行标记
{
dfs(i,j);
count++;
}
}
cout<<count;
return 0;
}有了这两个粒例子，相信大家开始对DFS有了一个大概的认识。
这一类问题就像我在刚刚导论里面提及的，如果这条路不同，则需要设置回溯，进行恢复现场。最经典的莫过于走迷宫问题（简单）：
/*
* @Author: your name
* @Date: 2022-01-22 21:06:31
* @LastEditTime: 2022-01-22 22:12:20
* @LastEditors: Please set LastEditors
* @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
* @FilePath: \All code\9.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN 505
bool vis[MAXN][MAXN];
char mp[MAXN][MAXN];
int row, cow;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
bool flag = false;
void dfs(int x, int y)
{
vis[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int newx = x + dx[i];
int newy = y + dy[i];
if (newx >= 0 && newy >= 0 && newx < row && newy < cow && vis[newx][newy] == 0)
{
if (mp[newx][newy] == '.')
dfs(newx, newy);
if (mp[newx][newy] == 'E')
flag = true;
}
}
}
void init()
{
for (int i = 0; i < row; i++)
for (int j = 0; j < cow; j++)
{
vis[i][j] = 0;
}
}
int main()
{
int i, j;
int count = 0;
int row_s, cow_s;
while (cin >> row >> cow)
{
flag = false;
for (i = 0; i < row; i++)
for (j = 0; j < cow; j++)
{
cin >> mp[i][j];
if (mp[i][j] == 'S')
{
row_s = i;
cow_s = j;
}
}
init();
dfs(row_s, cow_s);
if (flag == true)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
return 0;
}除此之外，还有一个例题，用于计数的：马走日
这个题只是将迷宫问题的路径选择和成功条件进行了一个改变，也是简单的搜索问题：
/*
* @Author: your name
* @Date: 2022-02-11 14:44:55
* @LastEditTime: 2022-02-11 15:30:56
* @LastEditors: Please set LastEditors
* @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
* @FilePath: \All code\28.cpp
*/
#include <iostream>
using namespace std;
#define MAXN 15
int mp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int row, cow, newx, newy;
int ans;
int dx[8] = { -2, -2, 2, 2, -1, -1, 1, 1 };
int dy[8] = { 1, -1, 1, -1, -2, 2, -2, 2 };
void init()
{
for (int i = 0; i < MAXN; i++)
{
for (int j = 0; j < MAXN; j++)
{
vis[i][j] = false;
}
}
ans = 0;
}
void dfs(int x, int y, int depth)
{
for (int i = 0; i < 8; i++)
{
int newx = x + dx[i];
int newy = y + dy[i];
if (newx >= 1 && newx <= row && newy >= 1 && newy <= cow && vis[newx][newy] == false)
{
vis[newx][newy] = true;
if (depth == row * cow - 1)//由于这里是newx，并不是已经递归到新一层中，所以这里需要减1
{
ans++;
}
dfs(newx, newy, depth + 1);
vis[newx][newy] = false;
}
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> row >> cow >> newx >> newy;
init();
vis[newx + 1][newy + 1] = true;
dfs(newx + 1, newy + 1, 1);//这里要注意，我在从第一步开始的时候，就已经算是处在第一层了，不是第0层。
cout << ans << endl;
}
return 0;
}我在开始这一道题的时候，就犯下了这样一个错误：将截止条件的层数看错。大家在写代码的时候要注意这个问题。
总结一下DFS的模板
function dfs(当前状态){
if(当前状态 == 目的状态){
···
}
for(···寻找新状态){
if(状态合法){
vis[访问该点]；
dfs(新状态);
?是否需要恢复现场->vis[恢复访问]
}
}
if(找不到新状态){
···
}
}
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[35];
bool dfs(int id, int sum)
{
if (sum == k)
return 1;
if (id > n)
return 0;
if (1 == dfs(id + 1, sum + a[id]))
return 1;
if (1 == dfs(id + 1, sum))
return 1;
return 0;
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
if (1 == dfs(1, 0))
{
puts("YES");
}
else
{
puts("NO");
}
return 0;
}
也很简单，只要一次在每一步中讨论当前这个数是否选取，即可。对于这个问题，如果是想要找出所有相加为k的序列中，个数最少的一个，也可以利用穷举的方法来写。同时也可以利用动态规划的知识来解题。读者可以下去自己思考。
我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll
深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal
寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是rubygems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和rubygems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko
我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/
我读了"BingSearchAPI-QuickStart"但我不知道如何在Ruby中发出这个http请求(Weary)如何在Ruby中翻译“Stream_context_create()”？这是什么意思？"BingSearchAPI-QuickStart"我想使用RubySDK，但我发现那些已被弃用前(Rbing)https://github.com/mikedemers/rbing您知道Bing搜索API的最新包装器(仅限Web的结果)吗？ 最佳答案 好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是
给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：
我有一个表，'jobs'和一个枚举字段'status'。status具有以下枚举集:enumstatus:[:draft,:active,:archived]使用ransack，我如何过滤表，比如说，所有事件记录？ 最佳答案 你可以像这样在模型中声明自己的掠夺者:ransacker:status,formatter:proc{|v|statuses[v]}do|parent|parent.table[:status]end然后您可以使用默认的搜索语法_eq来检查相等性，如下所示:Model.ransack(status_eq:'ac
我一直在使用postgres关注railscast的全文搜索，但我不断收到以下错误#的未定义局部变量或方法“作用域”我关注了railscast确切地。我安装了所有正确的gem。(pg_search，pg)。这是我的代码文章Controller(我在这里也使用acts_as_taggable)defindex@articles=Article.text_search(params[:query]).page(params[:page]).per_page(3)ifparams[:tag]@articles=Article.tagged_with(params[:tag])else@art
我想使用部分字符串搜索数组，然后获取找到该字符串的索引。例如:a=["Thisisline1","Wehaveline2here","andfinallyline3","potato"]a.index("potato")#thisreturns3a.index("Wehave")#thisreturnsnil使用a.grep将返回完整的字符串，使用a.any?将返回正确的true/false语句，但都不会返回匹配的索引找到了，或者至少我不知道该怎么做。我正在编写一段代码，该代码读取文件、查找特定header，然后返回该header的索引，以便它可以将其用作future搜索的偏移量。如果
深度学习12.CNN经典网络VGG16一、简介1.VGG来源2.VGG分类3.不同模型的参数数量4.3x3卷积核的好处5.关于学习率调度6.批归一化二、VGG16层分析1.层划分2.参数展开过程图解3.参数传递示例4.VGG16各层参数数量三、代码分析1.VGG16模型定义2.训练3.测试一、简介1.VGG来源VGG（VisualGeometryGroup）是一个视觉几何组在2014年提出的深度卷积神经网络架构。VGG在2014年ImageNet图像分类竞赛亚军，定位竞赛冠军；VGG网络采用连续的小卷积核（3x3）和池化层构建深度神经网络，网络深度可以达到16层或19层，其中VGG16和VGG