BFS算法示例 - 解开密码锁的最少次数
发布网友
发布时间：2023-05-25 20:55
共1个回答
热心网友
时间：2024-03-28 09:54
BFS(广度优先搜索)是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
BFS算法的核心思想就是把一些问题抽象成图.
BFS相对DFS最主要的区别是: BFS找到的路径一定是最短的,但代价是空间复杂度比DFS大很多.
BFS常出现的场景: 问题的本质就是让你在 一幅图 中找到从起点 start 到终点 target 的最近距离,BFS算法其实就是在干这事.
一般来说在找最短路径的时候用BFS,其他时候还是用DFS多一些.
传统的BFS框架是从起点开始向四周扩散,遇到终点时停止;而双向BFS则是从起点和终点同时开始扩散,当两边有交集的时候停止.
使用双向BFS的前提是,必须提前知道终点在哪里.
无论传统BFS还是双向BFS,无论做不做优化,从Big O 的衡量标准看,空间复杂度都是一样的.
有一个带四个圆形拨轮的转盘锁,每个拨轮都有0-9共10个数字,
每个拨轮可以上下旋转: 例如把9变成0, 0变成9,每次旋转只能将一个拨轮旋转 一下
