深度遍历与广度遍历有什么区别？

深度遍历（Depth-First Search, DFS）和广度遍历（Breadth-First Search, BFS）是图和树结构中常用的遍历方法。它们在访问节点的顺序和策略上有明显的不同。以下是它们的主要区别：

1. 深度遍历（DFS）

• 策略：优先深入到每个分支的尽头，然后回溯到上一个节点，继续探索其他未访问的分支。

• 数据结构：通常使用栈（可以是显式栈或递归调用的系统栈）来实现。

• 特点：

  • 遍历顺序：沿着树的深度方向进行，先访问子节点再访问兄弟节点。
  • 路径：可能找到到目标节点的一条路径，但不一定是最短路径。
  • 空间复杂度：在最坏情况下，栈的空间复杂度是 O(h)，其中 h 是树的高度。

• 示例：

  function dfs(node, visited) {
    if (node === null) return;
    console.log(node.value); // 访问节点
    visited.add(node); // 标记为已访问
    for (const neighbor of node.neighbors) {
      if (!visited.has(neighbor)) {
        dfs(neighbor, visited);
      }
    }
  }
  

2. 广度遍历（BFS）

• 策略：从根节点开始，逐层访问每个节点的所有直接子节点，然后再访问这些子节点的子节点，以此类推。

• 数据结构：通常使用队列来实现。

• 特点：

  • 遍历顺序：先访问当前层的所有节点，然后再访问下一层节点。
  • 路径：总是找到到目标节点的最短路径（如果图中的边权值相等）。
  • 空间复杂度：在最坏情况下，队列的空间复杂度是 O(w)，其中 w 是图中最大宽度（即最大层级节点数）。

• 示例：

  function bfs(startNode) {
    const queue = [startNode];
    const visited = new Set();
    visited.add(startNode);
  
    while (queue.length > 0) {
      const node = queue.shift(); // 从队列前端取出节点
      console.log(node.value); // 访问节点
  
      for (const neighbor of node.neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor); // 将未访问的邻居添加到队列
        }
      }
    }
  }