搜索理解(DFS BFS)

DFS:
         深搜是从当前位置一次所能到达的位置,一个位置一个位置的去查找,当遇到不能在行走时(即不符合条件时),return;返回到上一层函数,当试探完一个位置后要把标记取消,也就是所说的回溯;换一个方向继续查找直到查找完所有可以到达的地方,(当然,也可以找到一条符合条件的路线后,定义一个flag不再继续进行查找下去,返回就好了;注意第一次查找到的路线不一定是最快的,与广搜不同)。DFS因为一个一个的查找,所花费的时间比较多,也就出现了剪枝;其实也就是多加一些判断条件,不符合的话直接return返回上一层函数,不再进行一些无用的查找。

BFS:

         广搜是从当前的位置把一次所有能到达的位置,一下标记完,加入队列,也就是一层一层的查找;   每次从队首开始进行下一轮查找并更新队首,符合条件的点加入队列,步数加一;直到查找到想要的位置,结束查找。由于广搜是一层一层的查找所以最先找到的一定是最短路径而且时间比较短,基本上不会出现时间超限。自我感觉广搜主要还是对队列的理解;队列如果理解透的话,广搜只是对队列数据的判断。

全部评论

相关推荐

面试时长45分钟面完几个小时就显示终止了
MAGA让自动化再次...:评价是不如我电话约面后当晚终止
点赞 评论 收藏
分享
码农索隆:想看offer细节
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务