算法之深度优先遍历(DFS)和广度优先遍历(BFS)

JS 算法之深度优先遍历(DFS)和广度优先遍历(BFS)

深度优先遍历

该方法是以纵向的维度对 dom 树进行遍历，从一个 dom 节点开始，一直遍历其子节点，直到它的所有子节点都被遍历完毕之后在遍历它的兄弟节点。

递归实现：

/**
 * 深度优先遍历（递归实现）
 * @param data Array|Object
 */
function depthFirstTraverse(data) {
  const list = data instanceof Array ? data : [data];
  for (let i = 0; i < list.length; i++) {
    const node = list[i];
    console.log(node.id);
    node.child && depthFirstTraverse(node.child);
  }
}

Stack 实现：

/**
 * 深度优先遍历（stack实现）
 * @param data Array|Object
 */
function depthFirstTraverseStack(data) {
  const stack = data instanceof Array ? data : [data];
  while (stack.length > 0) {
    const node = stack.shift();
    console.log(node.id);
    node.child && stack.unshift(...node.child);
  }
}

广度优先遍历

该方法是以横向的维度对 dom 树进行遍历，从该节点的第一个子节点开始，遍历其所有的兄弟节点，再遍历第一个节点的子节点，完成该遍历之后，暂时不深入，开始遍历其兄弟节点的子节点。

递归实现：

/**
 * 广度优先遍历 （递归实现）
 * @param data Array|Object
 */
function breadthFirstTraverse(data) {
  let time = new Date().getTime();
  const list = data instanceof Array ? data : [data];
  let nextSibling = null;
  const nodes = [];
  let index = 0;

  function traverse(arr) {
    for (let i = 0; i < arr.length; i++) {
      const node = arr[i];
      nodes.push(node);
      console.log(node.id);
    }
    nextSibling = nodes[index++];
    nextSibling.child && traverse(nextSibling.child);
  }
  traverse(list);
  console.log(
    `广度优先遍历 （递归实现）耗时：${new Date().getTime() - time}ms`
  );
}

Queue 实现：

/**
 * 广度优先遍历 （队列实现）
 * @param  data Array|Object
 */
function breadthFirstTraverseQueue(data) {
  let time = new Date().getTime();
  const queue = data instanceof Array ? data : [data];
  while (queue.length > 0) {
    for (let i = 0; i < queue.length; i++) {
      const node = queue.shift();
      console.log(node.id);
      node.child && queue.push(...node.child);
    }
  }
  console.log(
    `广度优先遍历 （队列实现）耗时：${new Date().getTime() - time}ms`
  );
}