深度优先与广度优先搜索

🎯 引言

通过这篇文章，你将掌握如何用树结构来理解和实现深度优先搜索（DFS）和广度优先搜索（BFS）。你能清晰地分辨这两种遍历方式的不同思路和应用场景，学会在前端项目中处理树状数据，比如组件树遍历、菜单结构处理等常见任务。

🌳 什么是树结构？

在前端开发中，我们经常会遇到树这种数据结构，比如 DOM 树、组件树、文件目录树等等。

树由节点组成，每个节点都有零个或多个子节点，且节点之间是层级关系，没有环路。

举个简单的树例子：

        A
       / \
      B   C
     / \   \
    D   E   F

• 节点 A 是根节点（树的起点）
• 节点 B 和 C 是 A 的子节点
• 节点 D、E 是 B 的子节点，F 是 C 的子节点

🔍 深度优先搜索（DFS）在树中的遍历

深度优先搜索的核心是“尽可能深入每个分支”。

我们从根节点开始，先访问 A，然后访问 A 的第一个子节点 B，再访问 B 的第一个子节点 D。

访问到 D 后，D 没有子节点，我们回溯到 B，访问 B 的第二个子节点 E。

访问完 E 后回溯到 A，访问 A 的第二个子节点 C，最后访问 C 的子节点 F。

访问顺序是：A → B → D → E → C → F

🛠️ DFS 递归实现代码示例

这个树用对象表示：

const tree = {
    value: 'A',
    children: [
        {
            value: 'B',
            children: [
                { value: 'D', children: [] },
                { value: 'E', children: [] },
            ],
        },
        {
            value: 'C',
            children: [{ value: 'F', children: [] }],
        },
    ],
};

对应的深度优先遍历代码：

function dfs(node) {
    console.log(node.value);

    node.children.forEach(child => {
        dfs(child);
    });
}

dfs(tree);

执行结果是：

A
B
D
E
C
F

🔍 广度优先搜索（BFS）在树中的遍历

广度优先搜索的核心是“按层级访问”。

我们先访问根节点 A，然后访问 A 的所有子节点 B 和 C，再访问 B 和 C 的子节点 D、E、F。

访问顺序是：A → B → C → D → E → F

🛠️ BFS 队列实现代码示例

function bfs(root) {
    const queue = [root];

    while (queue.length > 0) {
        const node = queue.shift();
        console.log(node.value);

        node.children.forEach(child => {
            queue.push(child);
        });
    }
}

bfs(tree);

执行结果是：

A
B
C
D
E
F

🔄 DFS 和 BFS 在树遍历中的区别

• DFS 是先沿着一条路径“走到底”，再回溯访问其他路径
• BFS 是按层级访问，每一层的节点都会被访问完，才会进入下一层
• DFS 适合操作需要“先深入再回溯”的场景，比如查找特定节点、求解表达式树
• BFS 适合需要“分层处理”，比如渲染层级菜单、寻找树中距离根节点最近的目标节点

🧾 小节总结

• 树结构遍历常用 DFS 和 BFS 两种算法
• DFS 先“走深”，使用递归或栈实现，适合查找和深度操作
• BFS 先“走宽”，使用队列实现，适合分层处理和最短路径查找

❓ 知识问答（Q&A）

Q：DFS 怎么避免重复访问节点？
A：树结构本身没有环路，不存在重复访问问题。但图中要用集合记录已访问节点避免死循环。

Q：BFS 为什么用队列？
A：队列保证先进先出，符合按层访问节点的顺序。

Q：DFS 和 BFS 哪个更快？
A：这取决于具体问题，找最短路径一般 BFS 更优，遍历整棵树两者时间复杂度相同。

🎉 恭喜你已经掌握了深度优先搜索（DFS）、广度优先搜索（BFS）和树结构遍历这三项技能啦！祝你在前端学习路上越走越远！