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

Question

深度优先遍历（Depth-First Search，DFS）和广度优先遍历（Breadth-First Search，BFS）是两种常见的图或树的遍历算法。它们在遍历顺序和应用场景上有所不同，下面详细介绍这两种遍历方式。

1. 深度优先遍历（DFS）

基本思想

• 深度优先遍历的思想是从起始节点开始，尽可能沿着一个分支深入，直到不能再深入为止，然后回溯到上一个节点，继续遍历其他分支。该过程类似于树的前序遍历。

实现方式

• 递归实现 ：利用系统的函数调用栈实现。
• 非递归实现 ：使用显式的栈（stack）来模拟递归过程。

递归实现代码示例

// 以图的邻接表表示为例
function dfs(graph, start, visited = new Set()) {
    if (visited.has(start)) return;

    console.log(start); // 访问节点
    visited.add(start);

    for (let neighbor of graph[start]) {
        dfs(graph, neighbor, visited);
    }
}

// 示例图：邻接表表示
const graph = {
    A: ['B', 'C'],
    B: ['D', 'E'],
    C: ['F'],
    D: [],
    E: ['F'],
    F: []
};

dfs(graph, 'A');
// 输出顺序可能为：A -> B -> D -> E -> F -> C

非递归实现代码示例

function dfsIterative(graph, start) {
    const stack = [start];
    const visited = new Set();

    while (stack.length > 0) {
        const node = stack.pop();

        if (!visited.has(node)) {
            console.log(node); // 访问节点
            visited.add(node);

            // 将邻居节点入栈
            for (let neighbor of graph[node]) {
                stack.push(neighbor);
            }
        }
    }
}

dfsIterative(graph, 'A');
// 输出顺序可能为：A -> C -> F -> B -> E -> D

特点

• 优先深入 ：首先访问当前节点，然后递归访问该节点的子节点。
• 使用栈结构 ：递归时利用函数调用栈，或显式使用栈。
• 不保证最短路径 ：DFS 找到的路径不一定是最短路径。

应用场景

• 求解迷宫、数独等需要探索全部可能路径的问题。
• 拓扑排序。
• 连通性检测。

2. 广度优先遍历（BFS）

基本思想

• 广度优先遍历的思想是从起始节点开始，先访问该节点的所有邻居，然后依次访问这些邻居的邻居，逐层扩展，直到遍历完所有节点。该过程类似于树的层序遍历。

实现方式

• 使用队列（queue）来实现，先入先出（FIFO）。

实现代码示例

function bfs(graph, start) {
    const queue = [start];
    const visited = new Set();

    visited.add(start);

    while (queue.length > 0) {
        const node = queue.shift();
        console.log(node); // 访问节点

        for (let neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

bfs(graph, 'A');
// 输出顺序可能为：A -> B -> C -> D -> E -> F

特点

• 逐层访问 ：先访问当前节点的所有直接邻居，然后再访问下一层的邻居。
• 使用队列结构 ：利用队列存储当前层次的节点。
• 保证最短路径 ：在无权图中，BFS 找到的路径一定是最短路径。

应用场景

• 求解最短路径问题，如在无权图中寻找两点之间的最短路径。
• 寻找离散系统中的所有可能状态。
• 解决连通性、二分图等问题。

3. 对比 DFS 和 BFS

• 遍历顺序 ：
• DFS：优先探索深度，深入到最远的节点，然后回溯。
• BFS：按层次逐层探索，从近到远逐步扩展。
• 空间复杂度 ：
• DFS：如果使用递归，空间复杂度取决于递归深度；如果使用栈，栈的大小取决于最大递归深度（O(V)，V 为顶点数量）。
• BFS：使用队列，空间复杂度取决于每一层的宽度（最坏情况 O(V)）。
• 时间复杂度 ：两者在遍历整个图时的时间复杂度均为 O(V + E)，其中 V 为顶点数，E 为边数。
• 适用场景 ：
• DFS：适用于需要探索整个空间的场景，如迷宫问题、全排列问题等。
• BFS：适用于需要找到最短路径的场景，如找最短路径问题。

总结

• DFS 更适合需要完全探索所有可能路径的场景。
• BFS 更适合寻找最短路径或逐层解决问题的场景。

根据具体问题的需求选择合适的遍历算法，有时还需要结合具体数据结构和性能需求来综合考虑。

示例

深度优先遍历

let deepTraversal = (node, nodeList = []) => {
  if (node !== null) {
    nodeList.push(node)
    let children = node.children
    for (let i = 0; i < children.length; i++) {
      deepTraversal(children[i], nodeList)
    }
  }
  return nodeList;
}

广度优先遍历

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