关注
10、BFS+DFS
深搜,顾名思义,是深入其中、直取结果的一种搜索方法
如果深搜是一个人,那么他的性格一定倔得像头牛!他从一点出发去旅游,只朝着一个方向走,除非路断了,他绝不改变方向!除非四个方向全都不通或遇到终点,他绝不后退一步!因此,他的姐姐广搜总是嘲笑他,说他是个一根筋、不撞南墙不回头的家伙。
深搜很讨厌他姐姐的嘲笑,但又不想跟自己的亲姐姐闹矛盾,于是他决定给姐姐讲述自己旅途中的经历,来改善姐姐对他的看法。他成功了,而且只讲了一次。从那以后他姐姐不仅再没有嘲笑过他,而且连看他的眼神都充满了赞赏。他以为是自己路上的各种英勇征服了姐姐,但他不知道,其实另有原因……
深搜是这样跟姐姐讲的:关于旅行呢,我并不把目的地的风光放在第一位,而是更注重于沿路的风景,所以我不会去追求最短路,而是把所有能通向终点的路都走一遍。可是我并不知道往哪走能到达目的地,于是我只能每到一个地方,就向当地的人请教各个方向的道路情况。
深搜优缺点
①优点
能找出所有解决方案
优先搜索一棵子树,然后是另一棵,所以和广搜对比,有着内存需要相对较少的优点
② 缺点
要多次遍历,搜索所有可能路径,标识做了之后还要取消(在图中需要做标识)。
在深度很大的情况下效率不高
使用场景:性格测试的游戏
参考文章:https://segmentfault.com/a/1190000010563179
广搜,顾名思义,是多管齐下、广撒网的一种搜索方法
广搜属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。类似树的按层遍历,其过程为:首先访问初始点Vi,并将其标记为已访问过,接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2 … Vit,并均标记为已访问过,然后再按照Vi1、Vi2…Vit 的次序,访问每一个顶点的所有未被访问过的邻接点,并均标记为已访问过,依此类推,直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。
广搜优缺点
①优点
对于解决最短或最少问题特别有效,而且寻找深度小
每个结点只访问一遍,结点总是以最短路径被访问,所以第二次路径确定不会比第一次短
②缺点
内存耗费量大(需要开大量的数组单元用来存储状态,需要使用队列来保存遍历元素)
使用场景:计算网络数据链路层的最短跳数,走迷宫的最短路径
查看原帖
1 评论
相关推荐
点赞 评论 收藏
转发
查看18道真题和解析
点赞 评论 收藏
转发
牛客热帖
- 1... 美团后端日常实习面经9346
- 2... 【奖】这个夏天🍉,和牛牛一起打卡刷题~8984
- 3... 25暑期实习的心态变化 & 拥抱变化8623
- 4... 拼多多笔试 0526 24届算法6372
- 5... 【收集向】延毕了,影响工作吗?4988
- 6... 回首向来萧瑟处,也无风雨也无晴4686
- 7... 仰卧起坐了几个月才找到一个实习,但还是不满意。想着就这样吧,就约朋友一起去逛宜家,到了出发前两天觉得单独去太尴尬了,临时说要不要再喊一个朋友一起去,好玩一点。到了当天几乎是全程发呆,自闭。打车的时候她两手挽手在聊天,我感觉无所适从就蹲到边上的阴凉处了,一直想着要怎么遁了,感觉真的好尴尬啊。朋友看到了,突然问我一句你为什么要逃🥲,不是,怎么还有读心术啊。因为到了宜家已经中午十二点多了,就先排队打饭。我就继续站着发呆,朋友看到了就挥挥手,说一句hello?我一时有点懵,不知道这个时候是不是要回一句sever hello完成tls握手,还是要继续发呆假装服务器宕机了。吃饭的时候,聊天就我一直聊我找实习的事情,朋友不知道回我啥,就是给我夹菜😥,但我的菜好像都是一大块的,我不知道咋给她夹,就没夹。回去的时候我说了一句烧烤的事情,她问我要不要一起去吃烧烤,走到一半突然下起暴雨。我有伞但是不敢打开,谁懂谁懂谁懂。我们在路口等红绿灯,因为伞很小,我就往她那边靠,她发现之后问我有没有淋到,让我别淋坏了,然后把伞往我这边推。吃饭的时候她说本来想给我拍张照片发朋友圈的,因为我恰好看到她了,她就没好意思拍😂,我不知道说啥,过了一会问她,为什么她总是能这么开心,积极向上,感觉总是有无穷无尽的活力与能量,我感觉我怎么都开心不起来,所以我也不怎么发朋友圈,因为都是些负能量的事情,很多都是发了一会之后就仅自己可见了。因为我俩校区不一样,我一个人在等回去的车然后给家里人打了个电话,聊了聊家里情况只感到窒息,坐到椅子上蒙着眼睛一直哭,以前这些事情会让我感到开心,但现在不知道为什么很难开心起来了。第二天和我朋友去吃火锅,他们听完之后说了句乐土哥,你是不是养胃了?我想真是的,java毁了我4608
- 8... 27届JAVA后端4374
- 9... 用友技术笔试-友新星实习项目-Java-01卷4221
- 10... 鹅的暑期实习和毕业生提前实习的心态分享4174
正在热议
# 和牛牛一起刷题打卡 #
3900次浏览 384人参与
# 机械制造薪资爆料 #
340118次浏览 4037人参与
# 牛客帮帮团来啦!有问必答 #
975995次浏览 14942人参与
# 2022毕业生求职现身说法 #
20095次浏览 304人参与
# 你的简历改到第几版了 #
322718次浏览 4846人参与
# 通信硬件薪资爆料 #
241087次浏览 2273人参与
# 腾讯工作体验 #
145893次浏览 1404人参与
# 如何写一份好简历 #
299672次浏览 4317人参与
# 晒一晒我的offer #
3644459次浏览 56863人参与
# 产品人专业大盘点 #
15013次浏览 120人参与
# 金融银行面经 #
11556次浏览 187人参与
# 在国企工作的人,躺平了吗? #
105169次浏览 1332人参与
# 你觉得机械有必要实习吗 #
9958次浏览 130人参与
# 2023届毁约公司名单 #
97932次浏览 413人参与
# 运营人的第一份offer应该如何选 #
38219次浏览 664人参与
# 数据人的面试交流地 #
200966次浏览 4181人参与
# 23届的你们都什么时候入职? #
91193次浏览 779人参与
# 为什么国企只招应届生 #
55603次浏览 405人参与
# 浅聊一下我实习的辛苦费 #
92873次浏览 911人参与
# 2022毕业的你对23届的寄语 #
16158次浏览 346人参与