开发者社区> 问答> 正文

介绍下深度优先遍历和广度优先遍历,如何实现?

介绍下深度优先遍历和广度优先遍历,如何实现?

展开
收起
Bill 2020-05-23 13:49:54 2108 0
1 条回答
写回答
取消 提交回答
  • 领取2折优惠劵,有几率免单哦!http://www.weilai.info/tool/326.html

    从dom节点的遍历来理解这个问题

    image.png 我将用深度优先遍历和广度优先遍历对这个dom树进行查找

    深度优先遍历

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

    /*深度优先遍历三种方式*/
    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
    }
    

    image.png

    广度优先遍历

    广度优先遍历 BFS 从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。

    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
    }
    

    image.png

    2020-05-24 22:19:45
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载