本文转载自微信公众号“bigsai”,作者大赛。转载本文请联系bigsai公众号。前言如果你问一个人听说过哪些算法,那么深度优先搜索(dfs)和广度优先搜索(bfs)肯定在其中。很多小弟学完dfs和bfs感觉好像懂算法了,无所不能,确实如此。学习dfs和bfs暴力搜索枚举,确实是大部分人用超级强大的计算机计算都能找到的解法。学习dfs和bfs去暴力杯是一个很不错的选择!五个经典算法中的回溯算法其实是dfs的一个应用,不是召回被折磨的八个皇后。学习dfs和bfs的基础很容易,写模板代码也不难,但往往很难在此基础上变通。但是初步学习和理解dfs和bfs的原理还是比较简单的,但是要精通dfs和bfs还是有难度的,因为很多问题都是在这个基础上进行改造和优化的。比如你可能会考虑dfs的各种剪枝问题,而bfs可能会涉及到很多贪心策略,还有一些要考虑记忆的问题,双向bfs,bfs+dfs等等,这些都可以得到更好的解决。不过这篇文章比较基础,不同的扩展需要自己去研究。好的。邻接矩阵和邻接表dfs和bfs一般都是用来处理图论问题的,所以在看问题之前首先要注意图存储的问题。通常,邻接矩阵或邻接表用于存储图(对于交叉链表和压缩矩阵等空间优化不在此讨论)。邻接矩阵:邻接矩阵是一个数组(二维)来表示一个图。通常,我们会对这个图中每个节点的顺序进行编号,矩阵中的值表示这个图的连通性或者路径长度。如果是未加权图:布尔数组的01一般用来表示连通性。如果是带权图,则用数组的值表示两者之间路径的长度。如果为0,则表示未连接。另外,如果图是无向图,那么矩阵是对称的,如果是有向图,概率是不对称的。有关详细信息,请参阅以下示例。这种操作方式更有条理,操作起来也更方便。当然这种情况很容易造成空间浪费,所以有人进行空间优化,或者用邻接表的形式存储图。邻接表:观察上面的邻接矩阵,如果节点多但连接路径少,那么存储空间浪费太多,比较适合邻接表。邻接表一般是数组集链表,比邻接矩阵(直接存储联通信息或路径)节省空间,存储时可以根据数据格式要求灵活使用容器(如果是的话就省事了)没有正确的地图)。不过普通的无向图还是重复浪费了一半的空间,还有交叉链表,多链表等优化(大佬们的优化真的牛逼),只是算法逻辑略显复杂,但是一般的图论算法更注重算法的优化。这里不介绍交叉链表等。下图可以看到存储在邻接表中的图:深度优先搜索(dfs)概念:深度优先搜索是一种图算法,而英文缩写为DFS。深度优先搜索。过程就是深入每一个可能的分支路径,直到可以深入为止,并且每个节点只能访问一次。dfs简单的说就是在一个图中按照一定的规则进行搜索,一般是基于递归实现的,dfs对我们来说就像是一个黑魔法。算法设计好后会自动搜索,所以要注意算法的初始化、搜索规则、结束条件。二叉树的前序遍历是最简单的dfs遍历。我们通常使用邻接表或者邻接矩阵来存储图信息,而这里的例子使用邻接矩阵来完成!对于dfs的过程,大致可以这样认为:(1)一个节点开始往一个方向遍历到终点,同时标记已经走过的点。(2)遍历到终点后返回上一点,同时清除当前点的标记。向下一个方向遍历一次,然后继续重复步骤(1)。(3)直到所有过程完成,即返回起点。遍历过程中记得标记,因为不标记会死循环。标记表示该点已被使用不能使用,撤回标记表示该点可以再次使用。例如,对于一个全数组sai,在枚举s时,需要标记s不能使用(ssss不能一直进行下去),遍历到sa时a不能使用,sa会在第endofsai还是要回滚s。这时候a和i已经解决了,但是上次的索引方向是a(for循环到达的位置),那么下一次就需要往下一个方向i走,形成si,而然后以同样的方式返回到sia。从si到s,下面两个方向已经枚举出来了,所以还需要再回到sai,但是第一个方向s已经过了,剩下的从a开始的步骤可以类推。但是,完整的排列是一维空间中的dfs应用。标记时可以选择boolean数组对应的位置标记true为已使用,false表示未使用。另外,也可以使用动态数组List删除对应位置元素递归向下查找,然后在结束后插入对应位置(不是很推荐,效率比较低)。对于上图中的dfs,其中一个dfs搜索序列(可能有多个)可以用代码表示:publicclassdfs{staticbooleanisVisit[];publicstaticvoidmain(String[]args){intmap[][]=newint[7][7];isVisit=newboolean[7];地图[0][1]=地图[1][0]=1;地图[0][2]=地图[2][0]=1;地图[0][3]=地图[3][0]=1;地图[1][4]=地图[4][1]=1;地图[1][5]=地图[5][1]=1;地图[2][6]=地图[6][2]=1;地图[3][6]=地图[6][3]=1;isVisit[0]=true;dfs(0,map);//从0开始遍历;i
