当前位置: 首页 > 科技观察

Dfs和Bfs终于想通了

时间:2023-03-12 18:33:34 科技观察

本文转载自微信公众号“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开始遍历;i0&&isVisit[i]==false){isVisit[i]=true;dfs(i,map);}}System.out.println((index+1)+"Endofvisit");}}大致顺序访问就是BreadthFirstSearch(bfs)的概念:BFS,它的英文全称是BreadthFirstSearch。BFS不使用经验法则算法。从算法的角度来看,扩展一个节点产生的所有子节点都被添加到一个先进先出的队列中。在一般的实验中,邻居没有被检查过的节点会被放置在一个叫做open的容器中(比如队列或者链表),而被检查过的节点会被放置在一个叫做closedmiddle的容器中。(open-closedtable)简单来说,bfs就是从某个节点开始逐层遍历。估计大部分人第一次接触bfs的时候,都是在学习数据结构二叉树的层序遍历吧!借助队列层遍历。第二个估计是你学图论的时候,给你一张图,让你写一个bfs遍历序列,然后就没有bfs了。。。如果从路径上看,dfs就是个疯狗那跑的飞快,到处咬人,没路了就跑回别的地方继续,bfs就像一团毒气,缓缓延伸!在实现上,简单的bfs就是控制一个队列,后进先出进行层序遍历,但是很多时候可能会出现节点有正确值的场景,可能需要优先级队列。以上图为例,我们使用邻接表来实现一次bfs遍历。importjava.util.ArrayDeque;importjava.util.ArrayList;importjava.util.List;importjava.util.Queue;publicclassbfs{publicstaticvoidmain(String[]args){Listmap[]=newArrayList[7];booleanisVisit[]=newboolean[7];for(inti=0;i();}map[0].add(1);map[0.add(2);map[0].add(3);map[1].add(0);map[1].add(4);map[1].add(5);map[2.add(0);map[2].add(6);map[3].add(0);map[3].add(6);map[4].add(1);map[5.add(1);map[6].add(2);map[6].add(3);Queueq1=newArrayDeque();q1.add(0);isVisit[0]=true;while(!q1.isEmpty()){intva=q1.poll();System.out.println("Visit"+(va+1));for(inti=0;iset=newHashSet();//存储最终结果intn=Integer.parseInt(sc.nextLine());charmap[][]=newchar[n][n];for(inti=0;iq1=newArrayDeque();//左上队列Queueq2=newArrayDeque();//右下队列for(inti=0;iset1=newHashSet();//storezuoshangSetset2=newHashSet();//存储右下角q1。添加(新节点(i,n-1-i,""+map[i][n-1-i]));q2.add(新节点(i,n-1-i,""+map[i][n-1-i]));同时(!q1.isEmpty()&&!q2.isEmpty()){nodeteam=q1.poll();nodeteam2=q2.poll();if(team.x==n-1&&team.y==n-1)//到最后,存储路径{//System.out.println(team2.path);set1.add(team.path);set2.add(team2.path);}else{if(team.x0)//up{q2.add(newnode(team2.x-1,team2.y,team2.path+map[team2.x-1][team2.y]));}if(team2.y>0)//left{q2.add(newnode(team2.x,team2.y-1,team2.path+map[team2.x][team2.y-1]));}}}for(Stringva:set1){if(set2.contains(va)){set.add(va);}}}System.out.println(set.size());}}总结dfs和bfs很经典图论中的搜索算法,这两种算法的重要性都非常高,这里主要简单介绍一下,对于普通开发者来说,用dfs和bfs解决二叉树问题,迷宫搜索问题等简单的问题就足够了基础知识(面试官我对你来说不会那么难)如果很难理解,就多看教程,多做题。做多题之后,每道题算法运行的大概过程都有一个编号。