广度优先搜索(BFS)与深度优先搜索(DFS)的对比及优缺点

时间:2022-09-02 15:01:19

  深搜,顾名思义,是深入其中、直取结果的一种搜索方法。

  如果深搜是一个人,那么他的性格一定倔得像头牛!他从一点出发去旅游,只朝着一个方向走,除非路断了,他绝不改变方向!除非四个方向全都不通或遇到终点,他绝不后退一步!因此,他的姐姐广搜总是嘲笑他,说他是个一根筋、不撞南墙不回头的家伙。

  深搜很讨厌他姐姐的嘲笑,但又不想跟自己的亲姐姐闹矛盾,于是他决定给姐姐讲述自己旅途中的经历,来改善姐姐对他的看法。他成功了,而且只讲了一次。从那以后他姐姐不仅再没有嘲笑过他,而且连看他的眼神都充满了赞赏。他以为是自己路上的各种英勇征服了姐姐,但他不知道,其实另有原因……

  深搜是这样跟姐姐讲的:关于旅行呢,我并不把目的地的风光放在第一位,而是更注重于沿路的风景,所以我不会去追求最短路,而是把所有能通向终点的路都走一遍。可是我并不知道往哪走能到达目的地,于是我只能每到一个地方,就向当地的人请教各个方向的道路情况。为了避免重复向别人问同一个方向,我就给自己规定:先问北,如果有路,那就往北走,到达下一个地方的时候就在执行此规定,如果往北不通,我就再问西,其次是南、东,要是这四个方向都不通或者抵达了终点,那我回到上一个地方,继续探索其他没去过的方向。我还要求自己要记住那些帮过他的人,但是那些给我帮倒忙的、让我白费力气的人,要忘记他们。有了这些规定之后,我就可以大胆的往前走了,既不用担心到不了不目的地,也不用担心重复走以前的路。哈哈哈……

深搜优缺点
优点
1、能找出所有解决方案
2、优先搜索一棵子树,然后是另一棵,所以和广搜对比,有着内存需要相对较少的优点
缺点
1、要多次遍历,搜索所有可能路径,标识做了之后还要取消。
2、在深度很大的情况下效率不高

  广搜,顾名思义,是多管齐下、广撒网的一种搜索方法

  如果广搜是一个人,那么她一定很贪心,而且喜新厌旧!她从一点出发去旅游,先把与起点相邻的地方全部游览一遍,然后再把与她刚游览过的景点相邻的景点全都游览一边……一直这样,直至所有的景点都游览一遍。

  广搜属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。类似树的按层遍历,其过程为:首先访问初始点Vi,并将其标记为已访问过,接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2…Vit,并均标记为已访问过,然后再按照Vi1、Vi2…Vit 的次序,访问每一个顶点的所有未被访问过的邻接点,并均标记为已访问过,依此类推,直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。

广搜优缺点
优点
1、对于解决最短或最少问题特别有效,而且寻找深度小
2、每个结点只访问一遍,结点总是以最短路径被访问,所以第二次路径确定不会比第一次短
缺点
1、内存耗费量大(需要开大量的数组单元用来存储状态)