算法DFS (深度优先搜索)入门作为刚接触算法竞赛的大喜金鱼，第一次推出博客的我想在这里在csdn中记录我自己的成长。
DFS :全名是Depth First Search
是图论主题中重要的算法。
从我个人的理解来看，这个算法能解决的问题是小数据且有树枝的主题。 所述字母D和‘深度’可以被理解为从给定主题的根节点到叶节点的节点的数目。 它名为深度优先搜索，可以理解为以深度为基准点扫描所有数据的过程。
DFS算法的基本思想是利用函数的递归将题目所给出的条件树中的结点进行访问和判断操作，假设给定已知或已知最大深度判定条件的树，从根结点出发，遇到分支时选择随机道路
例如
此树的遍历条件为aBDIKIDEBEBFCGLGMOGHNP (此排序为超前遍历)
要确定是否继续递归操作，深度需要一个或多个数字作为依据。 例如，例题1的dep变量在dep达到最大值m时停止递归。
这里说明两个简单的例题；
1.) )第一题取自acwing的01背包问题注：本题数据庞大时应该使用动态规划的算法来解决
以一个最大容量和几件物品的价值和大小为主题问背包里能放的最大价值是多少
#includebits/stdc .h//万能头文件，参加竞赛的同学可以记录using namespace std的const int N=1005； int maxV，m，va[N]，V[N]，maxva=0； /*maxV是背包的容量，m是给定的道具数，maxva是可以容纳的最大价值，va和v的排列作为道具的价值和道具的大小，表示*/intmain((//这里把主函数写在前面void DFS scanf('%d%d )、m和maxV )； for(intI=0； im； I ) scanf('%d%d )、v ) I )、va ) I )； DFS (0，0，0 )； printf('%d '，maxva )； 返回0； }voidDFS(intdep，int sumV，int sumVa ) {//dep表示深度，sumv和sumva表示容量和价值的总和if (dep==m|||) return； //如果深度最大，或者行李总体积大于背包容积，如果深度最大，则所有有深度的行李将被选择或排除，返回，递归if(sumvamaxva ) maxva=sumva； DFS(dep1，sumV V[dep]，sumva va[dep] )； //选择这个深度的东西放入背包DFS(dep1、sumV、sumva )； //不选择那个深度的东西放入背包}输入输出
理解以上算法的关键在于，递归的作用是理解是否将该深度的东西放入背包。
2.
主题给定矩阵，求其上下左右和本身为一个的个数，在一端的情况下只考虑有数字的邻接部分即可。
# include bits/stdc.husingnamespacestd； const int N=1005； int mi[N][N]、pan[N][N]、col、row； //创建容纳矩阵块的mi数组，为了判断是否遍历，创建pan数组，col和row分别为行和列的int bex [4]={ 0，0，- 1，1 }，bey [4]={ 1，1，1 } //bex和bey函数在遍历上下左右数时更容易理解intmain(void )//这里以主函数为前提voiddfs ) int y，int y。 scanf('%d%d )、col、row )； for(intI=0； icol； I ) for(intj=0； row； j ) scanf('%d '，mi[i][j]； memset(pan，0，sizeof ) pan )； //pan阵列中的所有值都应为0 DFS (0，0 )； //(0，0 )到递归printf )“%d”，m )； }voidDFS(intx，int y ) (/x和y作为深度依据判断是否应该返回if(x=col||y=row||pan[x][y]！=0)返回；//当x或y深度达到或确定坐标点已过时时，pan[x][y]； //标记该坐标表示确定了该坐标是否满足主题要求m； //m值加1，如果下一个循环不满足主题条件，则恢复m值for (inti=0； i4； I ) if (xbex [ I ]=0x bex [ I ] coly bey [ I ]=0ybey [ I ] row ) /确定其周围四个点是否都是图中if(mi[xbex[I] )； }DFS(x1，y )； //用扩散方式遍历图中点DFS(x，y 1 )； DFS(x1，y 1； }输入输出：
本文是基于算法笔记的学习而写的，这两个问题在算法笔记第272页和第277页上进行了详细解说，发现第二个例题在算法笔记上的答案是4，用最传统的手法答案是5
这是我这个菜鸟第一次写这种博客类文章，还有许多不完美之处多多包涵。