广度优先搜索和深度优先搜索的实现
2023-02-18 16:30:12 时间
前言
广度优先搜索和深度优先搜索都是对图进行搜索的算法
广度优先搜索
广度优先搜索广泛搜索子节点,将其子节点放进候选节点中;操做候选节点时是按顺序取出候选节点,因此使用
队列
存储候选节点。关于队列的实现可参考队列的实现
- 声明广度优先搜索函数,参数为要搜索的树形图和要查找的节点
- 实例化队列,声明目标节点的深度,初始化0
- 遍历队列
- 获取队列第一个元素,判断是否和目标节点相等,相等返回深度
- 判断当前节点是否有子节点,并将子节点添加到队列中
- 删除当前队列第一个元素
function breadthFirstSearch(tree, target) {
//实例化队列
let queue = new Queue()
//声明目标节点的深度
let step = 0
//搜索树入队
queue.enqueue(tree)
//队列不为空就继续搜索
while(!queue.isEmpty()) {
//深度加一
step += 1
//获取队列长度
let length = queue.size()
//遍历队列
for(let i = 0; i < length; i++) {
//获取队列第一个元素
let front = queue.front()
//判断当前节点是否是要找的节点
if(target.value === front.value) return step
//判断当前节点是否有子节点并入队
if(front.children && front.children.length) {
front.children.map(item => {
queue.enqueue(item)
})
}
//删除已遍历过的节点
queue.dequeue()
}
}
}
广度优先搜索从一个顶点开始,先宽后深的访问节点,因此顶点离起点越近,搜索越快。
深度优先搜索
深度优先搜索将当前节点的直接子节点作为候选节点;操作候选节点时,采用最后加入的子节点,因此使用
栈
存储候选顶点;栈的实现
- 声明深度优先搜索函数,参数为要搜索的树形图和要查找的节点
- 数组模拟栈,将要搜索的树压入栈中
- 取出栈顶元素,判断是否是要查找的节点 如果是就返回当前节点
- 判断当前节点是否有子节点,翻转子节点组成的数组,压栈
function depthFirstSearch(tree, target) {
//数组模拟栈,将搜索的树形图压栈
let stack = [tree]
while(stack.length !== 0) {
//获取栈顶顶点
let stackTop = stack.pop()
//判断当前顶点是否是要查找的顶点
if(stackTop.value === target.value) return stackTop
//判断是否有子节点
if(stackTop.chilren && stackTop.children.length) {
//子节点组成的数组翻转,压栈
stack.push(...[...stack.children].reverse())
}
return false
}
}
广度优先搜索和深度优先搜索的区别
深度优先搜索:选择最新成为候补的顶点,沿着一条路径搜索到底
广度优先搜索:选择最早成为候补的顶点,沿着边搜索
相关文章
- java论坛贴子网站ssm论坛项目发帖子网站论坛系统论坛源码
- java美食论坛系统发帖子系统美食论坛网站美食分享论坛源码
- ACDSee 2023软件下载和安装教程
- ACDSee 2022软件下载和安装教程
- LPCG:用激光点云指导单目的3D物体检测
- ACDSee 2021软件下载和安装教程
- ACDSee 2020软件下载和安装教程
- ACDSee 2019软件下载和安装教程
- 深度学习算法原理——RCNN
- 2023年机器学习趋势分析
- 实时语义SLAM:激光+IMU+GPS/MAV
- VP-SLAM:具有点、线和灭点的单目实时VSLAM
- Adobe Acrobat 9 Pro软件安装教程(一款强大的PDF编辑软件)
- PDF编辑器Acrobat DC(PDF) 功能简介+安装破解
- PDF编辑软件:Adobe Acrobat DC
- Acrobat DC 2019 For Mac软件安装教程
- Acrobat Pro DC2021软件安装教程
- PE格式:VA地址与FOA地址
- PE格式:新建节并插入代码
- PE格式:新建节并插入DLL