深度优先和广度优先

广度优先算法

广度优先算法（BFS）是一种图形搜索算法，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果所有节点都被访问了，算法就会终止

其遍历顺序如下: img

BFS是一种盲目搜索法，也就是说，它不会考虑结果的可能地址，而是彻底地搜索整张图

所有因为展开节点而得到的子节点都会被放置在一个先进先出的队列中，一般情况下，其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中，检验过的就会放在closed容器中

加入有如下一段 html，需要用广度优先遍历，要求输出每个元素节点的tagName和className

<div class="root">
  <div class="container">
    <section class="sidebar">
      <ul class="menu"></ul>
    </section>
    <section class="main">
      <article class="post"></article>
      <p class="copyright"></p>
    </section>
  </div>
</div>

依照广度优先遍历算法我们可以得出这样的思路：

1621316295_1_.jpg

思路清晰了我们就可以开始着手代码了：

const traverse = (ndRoot) => {
  const queue = [ndRoot]
  while (queue.length) {
    const node = queue.shift()
    printInfo(node)
    if (!node.children.length) {
      continue
    }
    Array.from(node.children).forEach((x) => queue.push(x))
  }
}
const printInfo = (node) => {
  console.log(node.tagName, `.${node.className}`)
}
traverse(document.querySelector('.root'))
  1. 创建了一个数组queue来充当open队列
  2. 检查queue数组是否为空
    • 如果不为空，将数组第一个元素取出，输出这个元素的tagName和className
    • 如果为空，结束遍历
  3. 重新执行第二步

深度优先算法

深度优先算法（DFS）是用于遍历或搜索树或图数据结构的算法，该算法从根节点开始（在图的情况下选择一些任意节点作为根节点）并在回溯之前尽可能地沿着每个分支进行探索。

其遍历顺序如下： img

相对于广度优先搜索，深度优先搜索的实现要简单一些，只需要用递归就可以实现了，我们来整理一下思路：

思路清晰了我们就可以开始着手代码了：

const traverse = function (node) {
  if (!node) return
  printInfo(node)
  if (!node.children.length) return
  Array.from(node.children).forEach((item) => traverse(item))
}
const printInfo = (node) => {
  console.log(node.tagName, `.${node.className}`)
}
traverse(document.querySelector('.root'))
  1. 检查是否存在子节点
  • 存在，执行第二步
  • 不存在，退出当前函数
  1. 递归遍历子节点，输出元素的tagName和className
  2. 重新执行第一步