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

JavaScript016

JS 深度优先遍历(DFS)和广度优先遍历(BFS),第1张

深度优先遍历DFS

自定义：深度单线游走，从根走完最后一个节点，在游走兄弟节点，走完兄弟的所有子节点，循环之。

     递归算法：

function deepFirstSearch(node, nodeList = []) {

  if (node) {

    nodeList.push(node)

    var children = node.children

    for (var i = 0i <children.lengthi++)

      //每次递归的时候将 需要遍历的节点 和 节点所存储的数组传下去

      deepFirstSearch(children[i], nodeList)

  }

  return nodeList

}

非递归算法：

function deepFirstSearch(node) {

  var nodes = []

  if (node != null) {

    var stack = []

    stack.push(node)

    while (stack.length != 0) {

      var item = stack.pop()

      nodes.push(item)

      var children = item.children

      for (var i = children.length - 1i >= 0i--)

        stack.push(children[i])

    }

  }

  return nodes

}

广度优先遍历(BFS)

自定义：从根开始 层层推进 走完一层 走下一层 （犹如爬楼，走完一层的楼梯，继续下一层的楼梯）

递归算法：（容易栈溢出）

function breadthFirstSearch(node) {

  var nodes = []

  var i = 0

  if (!(node == null)) {

    nodes.push(node)

    breadthFirstSearch(node.nextElementSibling)

    node = nodes[i++]

    breadthFirstSearch(node.firstElementChild)

  }

  return nodes

}

非递归算法：（推荐）

function breadthFirstSearch(node) {

  var nodes = []

  if (node != null) {

    var queue = []

    queue.unshift(node)

    while (queue.length != 0) {

      var item = queue.shift()

      nodes.push(item)

      var children = item.children

      for (var i = 0i <children.lengthi++)

        queue.push(children[i])

    }

  }

  return nodes

}

Array | Iterable | AsyncIterable | Object的集合

需要执行的异步函数：有2种方式，普通带回调的函数，在函数之后最后必须调用回调函数传入err和result。如果err为空，则表明当前异步操作成功，将继续下一个异步执行，如果传入err不为空，则整个异步队列任务的状态即为false终止执行下面的任务。

另一种方式是es7的 async 函数,将return的值(即resolve的值)定义为此次的返回值，如果异常则自动将异常信息(即reject值）用于error信息

所有异步方法执行之后的回调函数，参数为err,results

如果方法中没有传入callback参数，则返回promise

方式一：传入callback

方式二：不传入callback，使用promise的then、catch方式

异步队列函数，同一时间并发执行的的函数的数量，仍属于异步，只不过做了每次执行的数量限制

异步串行执行，必须等到前一个异步任务状态sucess，才执行下一个任务。