[JavaScript]介绍下深度优先遍历和广度优先遍历，如何实现？

╰半橙微兮° 2022-11-30 01:39 126阅读 0赞

## 介绍下深度优先遍历和广度优先遍历，如何实现？ ##

**html代码**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center]  
**我将用深度优先遍历和广度优先遍历对这个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)
          for (let i = children.length - 1; i >= 0; i--) { 
          //注意，这里想节点输出顺序是从左往右，所以遍历顺序要从右往左入栈
            stack.push(children[i])
             //堆栈，后进先出
          }
        }
      }
      return nodes
    }

**输出结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 1]

#### 广度优先遍历 ####

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

let widthTraversal = (node) => { 
                let nodes = []
                let queue = []
                if (node) { 
                    queue.push(node)
                    while (queue.length) { 
                        let item = queue.shift()
                        nodes.push(item)
                        // 队列，先进先出
                        let children = item.children
                        for (let i = 0; i < children.length; i++) { 
                            queue.push(children[i])
                        }
                    }
                }
                return nodes
            }

**输出结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/feaecec5dbe14c6fa10ee34b7759306a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/411e56fff43f427caf70b0b995333b76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/29eb1a619cfc41f4a29ddaa8c4dc43f3.png