XmwDocs

主题

第 5 题：介绍下深度优先遍历和广度优先遍历，如何实现？ ​

我们从 DOM 节点的遍历来理解这个问题

html
<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>

使用深度优先遍历和广度优先遍历对 DOM 树进行查找

深度优先遍历 ​

深度优先遍历 DFS 与树的先序遍历比较类似。 假设初始状态是图中所有顶点均未被访问，则从某个顶点 v 出发，首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和 v 有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

js
/*深度优先遍历三种方式*/
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 的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

js
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;
};

输出结果：

总结 ​

  1. 深度优先遍历就是一种不撞南墙不会头的算法，他会把一条路走完之后再回溯到有分叉的节点继续遍历
  2. 广度优先搜索时，会从起点开始“一层一层”扩展的方法来遍历，扩展时每发现一个点就将这个点加入到队列，直到整张图都被遍历过位置