广度优先和深度优先

itvincent 发布于2019-08-26 10:25 / 1949人阅读

摘要：深度优先遍历和广度优先遍历什么是深度优先和广度优先其实简单来说深度优先就是自上而下的遍历搜索广度优先则是逐层遍历如下图所示深度优先广度优先两者的区别对于算法来说无非就是时间换空间空间换时间深度优先不需要记住所有的节点所以占用空间小而广度优先

深度优先遍历和广度优先遍历

什么是深度优先和广度优先

其实简单来说深度优先就是自上而下的遍历搜索广度优先则是逐层遍历, 如下图所示

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))

作者：zwmmm
链接：https://juejin.im/post/5c4a96...
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

云服务器 GPU云服务器广度优先遍历广度优先搜索 python广度优先广度优先搜索算法代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106142.html

数据结构与算法——广度和深度优先搜索

摘要：今天就来看看基于图的两种搜索算法，分别是广度优先搜索和深度优先搜索算法，这两个算法都十分的常见，在平常的面试当中也可能遇到。 1. 概论前面说到了图这种非线性的数据结构，并且我使用了代码，简单演示了图是如何实现的。今天就来看看基于图的两种搜索算法，分别是广度优先搜索和深度优先搜索算法，这两个算法都十分的常见，在平常的面试当中也可能遇到。在图上面的搜索算法，其实主要的表现形式就是从图...

shmily 2019-08-16 16:13 评论0 收藏0
深度优先搜索和广度优先搜索

摘要：不撞南墙不回头深度优先搜索基础部分对于深度优先搜索和广度优先搜索，我很难形象的去表达它的定义。这就是深度优先搜索了，当然，这个题目我们还有别的解法，这就到了我们说的广度优先搜索。不撞南墙不回头-深度优先搜索基础部分对于深度优先搜索和广度优先搜索，我很难形象的去表达它的定义。我们从一个例子来切入。输入一个数字n，输出1~n的全排列。即n=3时，输出123，132，213，231，...

huaixiaoz 2019-07-31 10:02 评论0 收藏0
JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

摘要：算法之深度优先遍历和广度优先遍历背景在开发页面的时候，我们有时候会遇到这种需求在页面某个节点中遍历，找到目标节点，我们正常做法是利用选择器，或者，但在本文，我们从算法的角度去查找节点，同时理解一下深度优先遍历和广度优先遍历的原理。 JS算法之深度优先遍历(DFS)和广度优先遍历(BFS) 背景在开发页面的时候，我们有时候会遇到这种需求：在页面某个dom节点中遍历，找到目标dom节点，...

roadtogeek 2019-08-23 16:33 评论0 收藏0
利用深度/广度优先遍历手动实现JavaScript对象的深度拷贝

摘要：引言搜索对象的深度拷贝，往往会冒出转换和递归拷贝大法。但遇到大数据量，它们都有调用栈爆栈的风险今天，我们尝试利用树的利用深度广度优先遍历来实现对象的深度拷贝。以下代码在环境下全部测试通过。引言搜索JavaScript对象的深度拷贝，往往会冒出JSON转换和递归拷贝大法。但遇到大数据量，它们都有调用栈爆栈的风险今天，我们尝试利用树的利用深度/广度优先遍历来实现对象的深度拷贝。以下代码...

RobinTang 2019-08-26 10:36 评论0 收藏0
实现深度遍历和广度遍历(递归与非递归版本)

摘要：先画个树，然后解释何为深度，何为广度第一层子集第二层子集第二层子集第三层，子集第三层第四层图就不画太复杂了，最高四层的结构，如果换成的形式的话可以理解成第一层第二层先画个树，然后解释何为深度，何为广度第一层子集 | ...

Betta 2019-08-26 10:09 评论0 收藏0