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

[Hanpoung]

深度优先遍历和广度优先遍历

这两个名词出现于一种叫做图的数据结构中，是两个遍历探索的算法：

• 深度优先

  • 对顶点A未被访问过的一个领节点进行深度探索，直到没有路径位置，此时进行回溯，在去探索A的其他未被探索的领节点，然后一直重复上述操作，直至全部被探索完毕为止
  • 
  • 访问过程：A->B->E（没有路了！回溯到A)->C->F->H->G->D（没有路，最终回溯到A,A也没有未访问的相邻节点，本次搜索结束）

• 广度优先

  • 顾名思义，对顶点A的未被访问过的领节点进行探索，然后继续探索未被探索的领节点的领节点，可以理解为逐层探索，直至这一层被探索完毕，探索下一层，往复上述操作，直至全部探索完毕

  • 

  • 访问过程：

    • 访问顶点V1
    • 访问V1的所有未被访问的领接点V2,V3....
    • 依次类推，知道全部被探索过为止

个人理解：

• 深度优先就是纵向探索，把一条纵向线探索完毕，然后回溯探索另一条线，一直重复这个过程，直到全部探索完毕
• 广度优先就是横向探索，把横向同级的领节点探索完毕，在继续探索下一层，一直重复这个过程，直到全部探索完毕

实现的方法有很多，这里我就直接套用atheist1的实现方法啦，从答案就能很清晰的看出深度优先和广度优先的区别~

再次申明，代码来自atheist1

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>

深度优先：

两种递归的方式
方法1：
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 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
}