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

参考答案：

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

1. 深度遍历（DFS）

策略：优先深入到每个分支的尽头，然后回溯到上一个节点，继续探索其他未访问的分支。
数据结构：通常使用栈（可以是显式栈或递归调用的系统栈）来实现。
特点：
- 遍历顺序：沿着树的深度方向进行，先访问子节点再访问兄弟节点。
- 路径：可能找到到目标节点的一条路径，但不一定是最短路径。
- 空间复杂度：在最坏情况下，栈的空间复杂度是 O(h)，其中 h 是树的高度。

示例：

javascript

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 是图中最大宽度（即最大层级节点数）。

示例：

javascript

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); // 将未访问的邻居添加到队列
            }
        }
    }
}

题目要点：

深度遍历（DFS）：
- 使用栈（递归调用栈或显式栈）。
- 适合需要彻底探索每个分支的场景。
- 不一定找到最短路径。
- 可能使用更多的内存，特别是在深度很大的树或图中。
广度遍历（BFS）：
- 使用队列。
- 适合寻找最短路径或按层级处理节点的场景。
- 可以保证找到最短路径（对于无权图）。
- 可能使用更多的内存，特别是在宽度很大的树或图中。

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

参考答案： ​

1. 深度遍历（DFS） ​

2. 广度遍历（BFS） ​

题目要点： ​

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

参考答案：

1. 深度遍历（DFS）

2. 广度遍历（BFS）

题目要点：