JavaScript中的深度优先遍历(DFS)和广度优先遍历(BFS)
深度优先：
深度优先遍历DFS 与树的先序遍历比较类似。
假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
深度优先遍历三种方式：
// 深度遍历
function interator(node) {
console.log(node);
if (node.children.length) {
for (var i = 0; i < node.children.length; i++) {
interator(node.children[i]);
}
}
}
// 非递归,首次传入的node值为DOM树中的根元素点，即html
// 调用：deep(document.documentElement)
function deep (node) {
var res = []; // 存储访问过的节点
if (node != null) {
var nodeList = []; // 存储需要被访问的节点
nodeList.push(node);
while (nodeList.length > 0) {
var currentNode = nodeList.pop(); // 当前正在被访问的节点
res.push(currentNode);
var childrens = currentNode.children;
for (var i = childrens.length - 1; i >= 0; i--) {
nodeList.push(childrens[i]);
}
}
}
return res;
}
// 使用递归
var res = []; // 存储已经访问过的节点
function deep (node) {
if (node != null) { // 该节点存在
res.push(node);
// 使用childrens变量存储node.children，提升性能，不使用node.children.length，从而不必在for循环遍历时每次都去获取子元素
for (var i = 0, childrens = node.children; i < childrens.length; i++) {
deep(childrens[i]);
}
}
return res;
}
广度优先：
广度优先遍历 BFS。
从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
广度优先遍历三种方式：
// 广度遍历
function interator(node) {
var arr = [];
arr.push(node);
while (arr.length > 0) {
node = arr.shift();
console.log(node);
if (node.children.length) {
for (var i = 0; i < node.children.length; i++) {
arr.push(node.children[i]);
}
}
}
}
// 递归
var res = [];
function wide (node) {
if (res.indexOf(node) === -1) {
res.push(node); // 存入根节点
}
var childrens = node.children;
for (var i = 0; i < childrens.length; i++) {
if (childrens[i] != null) {
res.push(childrens[i]); // 存入当前节点的所有子元素
}
}
for (var j = 0; j < childrens.length; j++) {
wide(childrens[j]); // 对每个子元素递归
}
return res;
}
// 非递归
function wide (node) {
var res = [];
var nodeList = []; // 存储需要被访问的节点
nodeList.push(node);
while (nodeList.length > 0) {
var currentNode = nodeList.shift(0);
res.push(currentNode);
for (var i = 0, childrens = currentNode.children; i < childrens.length; i++) {
nodeList.push(childrens[i]);
}
}
return res;
}
区别：
1.深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大。
2.深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点。
3.深度优先采用的是堆栈的形式, 即先进后出。
4.广度优先则采用的是队列的形式, 即先进先出。
作者：刘亦枫
