js实现深度优先遍历和广度优先遍历
2024-08-26 15:54:06
深度优先遍历和广度优先遍历
什么是深度优先和广度优先
其实简单来说 深度优先就是自上而下的遍历搜索 广度优先则是逐层遍历, 如下图所示
1.深度优先
2.广度优先
两者的区别
对于算法来说 无非就是时间换空间 空间换时间
- 深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大
- 深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点
深度优先采用的是堆栈的形式, 即先进后出
广度优先则采用的是队列的形式, 即先进先出
具体代码
const data = [
{
name: 'a',
children: [
{ name: 'b', children: [{ name: 'e' }] },
{ name: 'c', children: [{ name: 'f' }] },
{ name: 'd', children: [{ name: 'g' }] },
],
},
{
name: 'a2',
children: [
{ name: 'b2', children: [{ name: 'e2' }] },
{ name: 'c2', children: [{ name: 'f2' }] },
{ name: 'd2', children: [{ name: 'g2' }] },
],
}
]
// 深度遍历, 使用递归
function getName(data) {
const result = [];
data.forEach(item => {
const map = data => {
result.push(data.name);
data.children && data.children.forEach(child => map(child));
}
map(item);
})
return result.join(',');
}
// 广度遍历, 创建一个执行队列, 当队列为空的时候则结束
function getName2(data) {
let result = [];
let queue = data;
while (queue.length > 0) {
[...queue].forEach(child => {
queue.shift();
result.push(child.name);
child.children && (queue.push(...child.children));
});
}
return result.join(',');
}
console.log(getName(data))
console.log(getName2(data))
最新文章
- 调用手机在线API获取手机号码归属地信息
- Memo
- 固定IP 正常访问谷歌
- union all 里面的order by
- 最新 Sublime Text3 激活码 (Build 3114 有效)
- jar包里查找指定的class文件,排查是否存在或重复,工具软件:Java Class Finder
- POJ 3159 Candies (栈优化spfa)
- WARNING: 'aclocal-1.14' is missing on your system.
- C#如何发送邮件
- AI 玩法整理
- XamarinAndroid组件教程RecylerView适配器动画动画种类
- K-wolf Number (数位DP)
- 朴素贝叶斯分类器(Naive Bayes)
- c语言基本数据类型(short、int、long、char、float、double)
- Oracle中Instr用法
- CentOS 7.0 安装 ZCS 8.6.0
- 深度解析(一六)Floyd算法
- 模块(3)-使用__future__
- hadoop 2.7.3 (hadoop2.x)使用ant制作eclipse插件hadoop-eclipse-plugin-2.7.3.jar
- 【BZOJ 3925】[Zjoi2015]地震后的幻想乡 期望概率dp+状态压缩+图论知识+组合数学
热门文章
- 使用Default Trace查看谁还原了你的数据库?
- 最长不下降子序列 nlogn &;&; 输出序列
- Linux 一条长命令占用多行
- YAML_17 Playbook 综合
- 【转】根据Quartz-Cron表达式获取最近几次执行时间
- Problem 5 素数筛法+并查集
- BZOJ 1073: [SCOI2007]kshort
- 42、JDBC数据源案例
- 如何修复GitKraken Inotify Limit Error\idea erro - 升级Ubuntu / Linux inotify限制
- golang-笔记1