树与图

是什么，为什么存在

树（tree） 是由父子边连接的一组节点。在有根树中，一个节点是根，其余每个节点恰好有一个父节点，而且沿边形成的序列不会回到序列中已有的节点。这些约束形成了层级，并保证从根到每个节点都只有一条路径。

图（graph） 是更一般的模型：它由一组顶点和一组连接顶点的边构成。边可以有向或无向，也可以携带标签或权重。图可以包含环、通向同一顶点的多条路径、彼此断开的连通分量，以及没有任何边的顶点。

「节点」和「顶点」经常可以互换。树 API 通常使用节点，因为父节点、子节点、祖先和后代是核心概念。图算法通常使用顶点，因为边不一定表示所有权或层级。

这些模型之所以存在，是因为许多关系无法诚实地表示成一个扁平序列。文件系统、语法树、菜单和组织单元天然具有层级。包依赖、道路路线、社交关系、构建步骤和网页则形成一般网络。

树也是满足额外不变量的一种图。这些不变量让树算法可以省略不必要的机制。不过，一棵「树」一旦允许共享子节点、反向链接或多个父节点，即使记录仍有名为 children 的字段，也必须按图处理。

遍历把模型转化为操作。它选择起始顶点，按明确策略访问可达顶点，并执行收集名称、寻找目标、验证依赖或重建路线等工作。顺序属于算法契约，不是表面上的展示细节。

深度优先搜索与广度优先搜索回答不同问题。DFS 会先沿一个分支前进再返回，适合递归结构和回溯。BFS 按顶点与起点之间的边数逐层访问，因此是无权图最短路径的正确基线。

选择算法前，还要定义边的含义。依赖边可以从服务指向其依赖项，也可以采用相反方向。道路可能单向通行。颠倒约定会改变可达性，即使遍历代码本身正确，也可能回答错误的业务问题。

工作原理

根、顶点与边

有根树为遍历提供了天然起点。没有子节点的节点称为叶子；节点深度是它与根之间的边数。树高是最大的节点深度，但有些 API 会改为计算层数，因此结果相差 1。

图不要求存在根。应用需要提供起始顶点；如果必须覆盖断开的连通分量，就要从每个尚未访问的顶点启动遍历。可达性始终取决于边的方向和所选起点。

同样的五条记录可以在不同边关系下表达不同含义：

层级中每个非根节点都有一条入边表示其父节点。服务网络中，Checkout 有两条出边表示依赖，还存在一个经过 Pricing 与 Tax 的环。对于已经证明是树的数据，已访问集合可以省略；对于一般图遍历，它不可缺少。

表示形式也是契约

带有嵌套 children 字段的对象可以直接存储树。它很适合向下遍历，但代码如果还要向上移动，子节点通常需要显式保存父节点引用。即使逻辑数据仍是一棵树，增加父节点引用也会在内存对象图中形成环。

邻接表（adjacency list） 把每个顶点映射到它的出边邻居。在 JavaScript 中，可以直接用一个从稳定标识映射到数组的 Map 表示。它只存储实际存在的边，也让邻居迭代保持明确。

邻接矩阵会为每一对有序顶点分配一个单元格。它可以直接检查边是否存在，却要为全部顶点对分配空间，包括不存在的边。小型稠密图可能适合矩阵，而稀疏的依赖与路线数据通常更适合邻接表。

顶点标识必须有明确规则。两个对象实例可能描述同一个数据库实体，而两个显示名称相同的记录也可能是不同实体。遍历使用的已访问集合应采用领域认可的稳定标识，例如服务 ID 或车站代码。

邻居顺序也会影响可观察的遍历结果。DFS 和 BFS 只规定接下来处理哪种前沿结构，不会规定怎样排列原本无序的邻居。如果输出顺序有意义，就要存储顺序、按有文档说明的键排序，或者明确接受任意有效顺序。

深度优先搜索使用栈

深度优先搜索（depth-first search，DFS） 会选取一个未访问邻居继续前进，然后才返回处理其他选择。递归 DFS 使用语言的调用栈。迭代 DFS 则把待处理工作存入显式栈，避免把图的深度绑定到运行时递归限制。

基本的迭代 DFS 按以下方式转换状态：

1. 把起始顶点放入栈。
2. 弹出一个顶点；如果已经访问，就跳过。
3. 把它标为已访问并执行访问操作。
4. 按期望访问顺序的逆序压入邻居。
5. 持续处理，直到栈为空。

之所以要逆序压栈，是因为栈遵循后进先出。如果邻居为 [pricing, inventory]，且希望先访问 pricing，就要依次压入 inventory 和 pricing。递归循环无需反转，因为每次调用都会在循环继续前完成。

DFS 很适合计算递归结构、寻找连通分量、检测环，以及通过回溯探索搜索空间。单纯的 DFS 访问顺序不会自动变成依赖安装顺序。拓扑排序要求输入是有向无环图，还要记录完成顺序，而不只是发现顺序。

广度优先搜索使用队列

广度优先搜索（breadth-first search，BFS） 先访问起点，再访问相距一条边的顶点，然后访问相距两条边的顶点，并逐层继续。队列能保持这种层级顺序。加入一个未访问邻居，会把它留给之后的层处理，同时让较早入队的顶点继续排在前面。

基本的 BFS 采用稍有不同的状态转换：

1. 把起始顶点标为已发现并加入队列。
2. 从队列取出一个顶点并执行访问操作。
3. 对每个未发现邻居，将其标为已发现；如果需要则记录父节点，然后入队。
4. 持续处理，直到队列为空或找到指定目标。

入队时就做标记，可以防止同一层中的多个顶点重复加入同一个邻居。这也能保证第一次记录的父节点来自以最小边数发现该顶点的路径。等到出队后才标记，可能产生重复的前沿项，也会让父节点重建更复杂。

在无权图中，BFS 会按最少边数发现从起点可达的每个顶点。父节点映射保存每个顶点第一次被发现时使用的边。从目标反向跟随父节点，再反转收集到的序列，就能重建一条最短路径。

这项保证计算的是边数，而不是时间、价格或风险。如果边的成本不同，两条边的路线也可能差于三条边的路线。非负权重的最短路径需要 Dijkstra 等算法、优先队列以及明确的权重契约。

已访问状态保证遍历终止

已访问集合记录顶点的语义标识，不记录有多少条路径通向它。在环 A -> B -> C -> A 中，第二次遇到 A 时就会终止该分支。在菱形结构中，它能避免同一个共享目标经由每个父节点都被完整处理一次。

有时一个布尔状态还不够。有向环检测要区分未发现顶点、当前 DFS 路径上的活跃顶点，以及已经完成的顶点。遇到活跃顶点的边是反向边，可以证明存在有向环；遇到已完成顶点则不能得出这一结论。

除非 API 有意跨调用维护索引，否则遍历状态应只属于一次遍历。意外复用已访问集合，会让第二次搜索跳过有效顶点。把集合藏在模块状态中，还会让并发或交错执行的遍历彼此干扰。

示例

这些示例只使用 JavaScript 内置集合。每个文件都使用本地 Node 24 执行，紧随其后的 text 块就是对应的标准输出。

用前序遍历呈现分类树

这个目录是一棵用嵌套子节点表示的有根树。前序遍历会先访问节点再访问其后代，因此可以先输出父标签，再输出带缩进的子行。

每次递归调用都接收其所在路径拥有的深度，因此兄弟节点使用相同缩进，子节点则增加一级。代码依赖树契约：每条记录都有 children 数组，而且子节点不会指回祖先。

如果数据来自 API，应在递归前验证这些假设。缺少 children 字段属于模式错误；存在环则表示逻辑输入是一张图，需要跟踪已访问状态或直接拒绝。

用 DFS 遍历有环的服务依赖

这个邻接表包含 pricing -> tax -> catalog -> pricing。已访问集合让遍历能够终止，显式栈则消除了对调用栈的依赖。

const dependencies = new Map([
  ["checkout", ["pricing", "inventory"]],
  ["pricing", ["tax"]],
  ["tax", ["catalog"]],
  ["catalog", ["pricing"]],
  ["inventory", ["catalog"]],
]);

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

  while (stack.length > 0) {
    const service = stack.pop();
    if (visited.has(service)) continue;

    visited.add(service);
    order.push(service);

    const next = graph.get(service) ?? [];
    for (let index = next.length - 1; index >= 0; index -= 1) {
      stack.push(next[index]);
    }
  }

  return order;
}

console.log(depthFirst(dependencies, "checkout").join(" -> "));

checkout -> pricing -> tax -> catalog -> inventory

逆序压入邻居，让这次 DFS 的结果保留邻接数组从左到右的顺序。这个结果只表示可达性顺序。环的存在说明图没有有效的拓扑顺序，而且这个函数也没有尝试生成拓扑顺序。

?? [] 策略把缺失的映射项当作没有出边的顶点。对于不完整数据，这可能很方便；但依赖验证器也可能选择报告所有只有引用、没有自身条目的服务。

用 BFS 重建无权路线

路线映射使用有向连接。BFS 第一次把地点加入队列时记录其父节点；只有发现目标后，才会反向跟随父节点。

const routes = new Map([
  ["Depot", ["Museum", "Station"]],
  ["Museum", ["Park"]],
  ["Station", ["Harbor"]],
  ["Park", ["Harbor"]],
  ["Harbor", []],
]);

function shortestPath(graph, start, goal) {
  const queue = [start];
  const seen = new Set([start]);
  const parent = new Map([[start, null]]);
  let head = 0;

  while (head < queue.length) {
    const place = queue[head];
    head += 1;
    if (place === goal) break;

    for (const neighbor of graph.get(place) ?? []) {
      if (seen.has(neighbor)) continue;
      seen.add(neighbor);
      parent.set(neighbor, place);
      queue.push(neighbor);
    }
  }

  if (!parent.has(goal)) return null;

  const path = [];
  for (let place = goal; place !== null; place = parent.get(place)) {
    path.push(place);
  }
  return path.reverse();
}

const harborRoute = shortestPath(routes, "Depot", "Harbor");
const airportRoute = shortestPath(routes, "Depot", "Airport");
console.log(harborRoute.join(" -> "));
console.log(airportRoute ?? "No route");

Depot -> Station -> Harbor
No route

Harbor 第一次经由 Station 被发现，距离为两条边。经过 Museum 和 Park 的替代路线需要三条边，无法取代这个父节点。目标不存在时返回 null，而不是一条不完整路线。

头索引避免每次出队都删除数组的第一个元素。已消费的前缀会一直分配到函数返回，这对于有界遍历很合适。长期运行的流式队列则应使用能够回收存储空间的队列抽象。

陷阱

把图数据当作树

修复： 在边界处验证承诺为树的数据，或者用稳定顶点标识按图遍历。测试自环、双顶点环，以及两个父节点共享一个目标的菱形结构。

等到出队后才标记 BFS 顶点

修复： 邻居入队时就同步标为已发现，而且只设置一次父节点。用菱形图测试，并同时断言路径和入队顶点数量。

把数组头部用作无界队列

修复： 像路线示例一样，为遍历期间使用的数组保留头索引；长期队列则使用经过测试的双端队列。还要对外部提供的图设置明确规模上限。

把 BFS 当成带权最短路径算法

修复： 明确所有边是否成本相等。非负权重应采用合适的带权算法，拒绝非法权重，并测试最便宜路线拥有更多边的情况。

把 DFS 发现顺序当成依赖顺序

修复： 明确要求拓扑排序，使用三状态环检测，并在失败时返回有用的环路径。除了依赖环，也要测试独立的连通分量。

对无界深度使用递归

修复： 深度没有严格上限时使用显式栈，并执行符合服务约束的输入限制。除了平衡样例树，还要测试长链。

延伸阅读

• MDN：Map
• MDN：Set
• NIST 词典：广度优先搜索
• NIST 词典：深度优先搜索
• Princeton Algorithms：图