Skip to content

1. 先区分处理顺序 ​

深度优先是 DFS / Depth First Search,广度优先是 BFS / Breadth First Search。前者先沿一个分支深入,后者按离起点的边数分层。旧文曾将英文名称颠倒,并在递归时重复传入当前节点;本篇改用可独立测试的普通树对象。

输入为有限、无环且无共享节点的多叉树,节点有 value 和数组 children,空树为 null。这同样适用于菜单树;真实 DOM 有不同字段和实时集合,使用前须明确转换与遍历期间是否允许修改。

2. 显式栈的深度优先 ​

栈后进先出。若希望孩子从左到右访问,就按从右到左的顺序入栈。

js
function depthFirst(root) {
    if (root === null) return [];
    const stack = [root];
    const result = [];
    while (stack.length) {
        const node = stack.pop();
        result.push(node.value);
        for (let i = node.children.length - 1; i >= 0; i--) stack.push(node.children[i]);
    }
    return result;
}

时间为 O(n),输出为 O(n);显式栈最多可能存多个尚未展开的兄弟,在一般多叉树上辅助空间最坏为 O(n),不要一概写成树高。

3. 队列的广度优先 ​

js
function breadthFirst(root) {
    if (root === null) return [];
    const queue = [root];
    const result = [];
    for (let head = 0; head < queue.length; head++) {
        const node = queue[head];
        result.push(node.value);
        for (const child of node.children) queue.push(child);
    }
    return result;
}

时间为 O(n),本数组队列保留全部已读引用,辅助空间为 O(n),输出也为 O(n)。两者不修改输入。

4. 从树走向图 ​

树中每个节点只有一个父节点,合法输入无需防止从另一条边再次到达。图可能有环和多条路径,必须维护访问标记。广度优先通常在入队时标记,避免同一顶点被不同父节点反复加入。

任务优先考虑理由
子树汇总、回溯路径深度优先便于沿分支维护状态和返回
无权最短步数、逐层处理广度优先第一次到达对应最少边数
带权最短路根据权重选算法普通广度优先不比较总权重

图的可运行实现统一见图专题,网格实例见网格搜索。

5. 手推与验收 ​

根 A 的孩子为 B、C,B 的孩子为 D:深度顺序为 A B D C,广度顺序为 A B C D。自己在每一步写出栈或队列内容;检查空树、长链和多个孩子。

sh
node --test tests/algorithm-tree-graph-examples.test.mjs

评论

正在加载评论…