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