一些算法在前端方面也有作用，比如 DFS/BFS 在前端可以进行对象的深拷贝、DOM 树遍历、数组扁平化等等。

例如，有下面一个待遍历的 DOM 树：

<body>
  <div class="parent">
    <div class="child-1">
      <div class="child-1-1">
        <div class="child-1-1-1">a</div>
      </div>
      <div class="child-1-2">
        <div class="child-1-2-1">b</div>
      </div>
      <div class="child-1-3">c</div>
    </div>
    <div class="child-2">
      <div class="child-2-1">d</div>
      <div class="child-2-2">e</div>
    </div>
    <div class="child-3">
      <div class="child-3-1">f</div>
    </div>
  </div>
</body>

深度优先遍历（DFS）

深度优先遍历 DFS 与树的先序遍历比较类似。

  1. 假设初始状态是图中所有顶点均未被访问，则从某个顶点 v 出发，首先访问该顶点
  2. 从该顶点开始沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点 v 的所有边都已被探寻过，将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止。
  3. 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

三种（其实是两种：递归/非递归）深度优先遍历

// 使用全局变量 nodeList
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;
}

// 使用局部变量 nodeList，每次进行拼接
let deepTraversal2 = (node) => {
  let nodeList = [];
  if (node !== null) {
    nodeList.push(node);
    let children = node.children;
    for (let i = 0; i < children.length; i++) {
      nodeList = nodeList.concat(deepTraversal2(children[i]));
    }
  }
  return nodeList;
}

// 使用栈，非递归
let deepTraversal3 = (node) => {
  let stack = [];
  let nodeList = [];
  if (node) {
    stack.push(node);
    while (stack.length !== 0) {
      // 取出栈顶部的元素，也就是后入栈的“子元素”
      let item = stack.pop();
      nodeList.push(item);
      let children = item.children;
      // 因为每次从尾部取元素，所以倒序推入才能正序取出
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i]);
      }
    }
  }
  return nodeList;
}

广度优先遍历（BFS）

广度优先遍历 BFS 与树的层次遍历比较类似。

  1. 从图中某顶点 v 出发，在访问了 v 之后依次访问 v 的各个未曾访问过的邻接点
  2. 分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
  3. 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
// 使用队列
let widthTraversal2 = (node) => {
  let nodeList = [];
  let queue = [];
  if (node) {
    queue.push(node);
    while (queue.length !== 0) {
      // 取出队列前端的元素，也就是先入队列的“父元素”
      let item = queue.shift();
      nodeList.push(item);
      let children = item.children;
      for (let i = 0; i < children.length; i++) {
        queue.push(children[i]);
      }
    }
  }
  return nodeList;
}

更多文章请关注《万象专栏》