JS中的广度与深度优先遍历

发表于

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

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

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

1.深度优先

image
2.广度优先

image

两者的区别

对于算法来说 无非就是时间换空间 空间换时间

  1. 深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大
  2. 深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点

深度优先采用的是堆栈的形式, 即先进后出
广度优先则采用的是队列的形式, 即先进先出

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
const data = [{
		name: 'a',
		children: [{
				name: 'a1',
				children: [{
					name: 'a11'
				},{
					name: 'a12'
				}]
			},
			{
				name: 'a2',
				children: [{
					name: 'a21'
				},{
					name: 'a22'
				}]
			},
			{
				name: 'a3',
				children: [{
					name: 'a31'
				},{
					name: 'a32'
				}]
			},
		],
	},
	{
		name: 'b',
		children: [{
				name: 'b1',
				children: [{
					name: 'b11'
				},{
					name: 'b12'
				}]
			},
			{
				name: 'b2',
				children: [{
					name: 'b21'
				},{
					name: 'b22'
				}]
			},
			{
				name: 'b3',
				children: [{
					name: 'b31'
				},{
					name: 'b32'
				}]
			},
		],
	}
];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 深度遍历, 使用递归
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(',');
}

console.log(getName(data));
//  a,a1,a11,a12,a2,a21,a22,a3,a31,a32,b,b1,b11,b12,b2,b21,b22,b3,b31,b32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 广度遍历, 创建一个执行队列, 当队列为空的时候则结束
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(getName2(data));
// a,b,a1,a2,a3,b1,b2,b3,a11,a12,a21,a22,a31,a32,b11,b12,b21,b22,b31,b32

从JS遍历DOM树学算法

js实现深度优先遍历和广度优先遍历

JS 中的广度与深度优先遍历

数组和链表对比总结

  • 数组静态分配内存，链表动态分配内存;
  • 数组在内存中连续，链表不连续;
  • 数组元素在栈区，链表元素在堆区;
  • 数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n);
  • 数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1);

栈、堆、队列深入理解，面试无忧

JavaScript数据结构之-队列

JavaScript数据结构之-栈

Event Loop

用 JavaScript 实现常用数据结构,栈,队列,链表,哈希表,二叉搜索树

JavaScript变量——栈内存or堆内存

栈 是一种遵循 后进先出（LIFO） 原则的有序集合。

堆和栈这两个字我们已经接触多很多次，那么具体是什么存在栈中什么存在堆中呢？就拿 JavaScript 中的变量来说：

首先 JavaScript 中的变量分为基本类型和引用类型。

基本类型就是保存在栈内存中的简单数据段，而引用类型指的是那些保存在堆内存中的对象。

基本类型

基本类型有 Undefined、Null、Boolean、Number 和String。这些类型在内存中分别占有固定大小的空间，他们的值保存在栈空间，我们通过按值来访问的。

引用类型

引用类型，值大小不固定，栈内存中存放地址指向堆内存中的对象。是按引用访问的。如下图所示：栈内存中存放的只是该对象的访问地址， 在堆内存中为这个值分配空间 。 由于这种值的大小不固定，因此不能把它们保存到栈内存中。但内存地址大小的固定的，因此可以将内存地址保存在栈内存中。 这样，当查询引用类型的变量时， 先从栈中读取内存地址， 然后再通过地址找到堆中的值。对于这种，我们把它叫做按引用访问。

其他语言中的内存分配类似。

PS：当我们看到一个变量类型是已知的，就分配在栈里面，比如INT,Double等。其他未知的类型，比如自定义的类型，因为系统不知道需要多大，所以程序自己申请，这样就分配在堆里面。

为什么会有栈内存和堆内存之分？

通常与垃圾回收机制GC有关。为了使程序运行时占用的内存最小。

当一个方法执行时，每个方法都会建立自己的内存栈，在这个方法内定义的变量将会逐个放入这块栈内存里，随着方法的执行结束，这个方法的内存栈也将自然销毁了。因此，所有在方法中定义的变量都是放在栈内存中的；

当我们在程序中创建一个对象时，这个对象将被保存到运行时数据区中，以便反复利用（因为对象的创建成本通常较大），这个运行时数据区就是堆内存。堆内存中的对象不会随方法的结束而销毁，即使方法结束后，这个对象还可能被另一个引用变量所引用（方法的参数传递时很常见），则这个对象依然不会被销毁，只有当一个对象没有任何引用变量引用它时，系统的垃圾回收机制才会在核实的时候回收它。

什么是堆？什么是栈？js内存机制是什么？

任何一种语言都有数据类型的分类，某种语言是如何存放和分配这些数据的，这就是内存管理。那栈和堆与内存有什么关联呢? 首先要理解的是栈和堆也就是栈内存和堆内存, 它们都存放于内存中.

堆内存

用于存储Js中的复杂数据类型，当我们创建一个对象或数组或new一个实例的时候，就会在堆内存中开辟一段空间给它，用于存放。
堆内存可以动态地分配内存大小，生存期也不必事先告诉编译器，因为它是在运行时动态分配内存的，但缺点是，由于要在运行时动态分配内存，存取速度较慢。

深入js基础：从内存机制、解析机制到执行机制（长文预警）

栈内存

用于存储Js中的简单数据类型及对象的引用指针, 该指针指向的是堆内存中对应的值
栈内存的特点是后进先出, 可以直接存取的，而堆内存是不可以直接存取的内存。对于我们的对象来数就是一种大的数据类型而且是占用空间不定长的类型，所以说对象是放在堆里面的，但对象名称是放在栈里面的，这样通过对象名称就可以使用对象了。

进程与线程

对于进程和线程傻傻分不清？没关系，老规矩，上定义：

  • 进程是操作系统分配资源和调度任务的基本单位
  • 线程是建立在进程上的一次程序运行单位，一个进程上可以有多个线程。