介绍下深度优先遍历和广度优先遍历，如何实现？
个人题解
没有做过相关的内容,猜测
深度优先遍历
先找到一个节点, 遍历到当前节点最深的目录
广度优先遍历
优先遍历当前一级的节点,然后再遍历下一层节点
最高赞题
- 第五题问的是深度优先遍历和广度优先遍历，我是从dom节点的遍历来理解这个问题的
- html代码
- 我将用深度优先遍历和广度优先遍历对这个dom树进行查找
深度优先遍历
深度优先遍历DFS 与树的先序遍历比较类似。
假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
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
| /*深度优先遍历三种方式*/
let deepTraversal1 = (node, nodeList = []) => {
if (node !== null) {
nodeList.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
deepTraversal1(children[i], nodeList)
}
}
return nodeList
}
let deepTraversal2 = (node) => {
let nodes = []
if (node !== null) {
nodes.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
nodes = nodes.concat(deepTraversal2(children[i]))
}
}
return nodes
}
// 非递归
let deepTraversal3 = (node) => {
let stack = []
let nodes = []
if (node) {
// 推入当前处理的node
stack.push(node)
while (stack.length) {
let item = stack.pop()
let children = item.children
nodes.push(item)
// node = [] stack = [parent]
// node = [parent] stack = [child3,child2,child1]
// node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
// node = [parent, child1-1] stack = [child3,child2,child1-2]
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i])
}
}
}
return nodes
}
|
输出结果
广度优先遍历
广度优先遍历 BFS
从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| let widthTraversal2 = (node) => {
let nodes = []
let stack = []
if (node) {
stack.push(node)
while (stack.length) {
let item = stack.shift()
let children = item.children
nodes.push(item)
// 队列，先进先出
// nodes = [] stack = [parent]
// nodes = [parent] stack = [child1,child2,child3]
// nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
// nodes = [parent,child1,child2]
for (let i = 0; i < children.length; i++) {
stack.push(children[i])
}
}
}
return nodes
}
|
输出结果
相关链接
第 5 题：介绍下深度优先遍历和广度优先遍历，如何实现？ #9