前端知库

前端场景中的图遍历应该怎样建模？

用模块依赖和页面路由图说明 BFS、DFS、访问集合和环检测的区别，给出可复用实现并分析复杂度、深度风险和异步遍历边界。

参考答案

简答

  • 图通常用邻接表（Map 加数组）表示，遍历前要明确边的方向。
  • DFS 用显式栈逐条路径深入，BFS 用队列按层扩展，能找到边数最少的路径。
  • visited 集合用来防止环导致的死循环和共享节点的重复处理。
  • 时间复杂度是 O(V + E)，起点不存在时两种遍历都返回 null。

前端工程里的依赖关系、页面跳转、权限继承和节点连接都可以表示成图：节点是模块或页面，边是“依赖”“可以跳转到”或“引用”。一旦图中存在共享节点、回路或多个入口，单纯递归一个数组就容易重复处理、死循环或无法解释访问顺序。

先确定图的方向和数据结构

有向图的边有方向，例如模块 A 导入模块 B；无向图的边表示双方关系，例如两个节点直接相连。遍历前要明确“从哪里出发”和“沿什么边走”，否则“找到所有相关页面”可能有多种不同答案。

前端接口常用邻接表表示：

JavaScript
const dependencies = new Map([
  ['app', ['router', 'ui']],
  ['router', ['url']],
  ['ui', ['button']],
  ['button', []],
  ['url', []],
]);

Map 的键是节点 ID，值是直接邻居。真实数据应校验节点 ID、邻居数组和缺失节点策略；不能把服务器返回的任意对象直接当作可遍历图，还要限制节点数量和边数量，避免输入造成资源耗尽。

DFS 适合沿一条路径深入

深度优先搜索先沿当前邻居继续向下，走不通后再回退。它适合依赖分析、路径存在性和拓扑相关检查，但递归实现的调用深度受 JavaScript 栈限制。

JavaScript
function depthFirst(start, graph, visit) {
  if (!graph.has(start)) return null;
  const visited = new Set();
  const stack = [start];

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

    const neighbors = graph.get(node) ?? [];
    for (let index = neighbors.length - 1; index >= 0; index -= 1) {
      if (!visited.has(neighbors[index])) stack.push(neighbors[index]);
    }
  }
  return visited;
}

起点不在图中时，DFS 与下面的 BFS 都返回 null，调用方可以统一判断。这里用显式栈避免深图递归溢出。逆序压栈只是为了让访问顺序更接近邻接表从左到右；如果业务只关心可达集合，顺序不应被实现细节当成契约。

BFS 适合按层寻找最短边数

如果每条边成本相同，BFS 按距离一层层扩展，第一次到达目标时得到的是边数最少的路径。它适合查找页面跳转的最少步骤、组件依赖层级或最近的可达节点。

JavaScript
function shortestPath(start, target, graph) {
  if (!graph.has(start)) return null;
  const queue = [start];
  let head = 0;
  const previous = new Map([[start, null]]);

  while (head < queue.length) {
    const node = queue[head++];
    if (node === target) break;

    for (const neighbor of graph.get(node) ?? []) {
      if (previous.has(neighbor)) continue;
      previous.set(neighbor, node);
      queue.push(neighbor);
    }
  }

  if (!previous.has(target)) return null;
  const path = [];
  for (let node = target; node !== null; node = previous.get(node)) {
    path.push(node);
  }
  path.reverse();
  return path;
}

head 指针避免每次 shift() 搬移整个数组。previous 同时承担访问集合和回溯路径的职责：第一次写入一个节点时记录它从哪里到达，后续遇到同一节点就跳过。

这只保证边数最少，不保证真实页面加载时间最短。如果边有权重，例如网络延迟或费用，就要使用 Dijkstra、A* 或其他适合权重的算法；不能把 BFS 的结果叫作所有场景的“最优路径”。

访问集合是防止重复和环的关键

有向图可以包含 A → B → C → A。没有 visited 集合，DFS 或 BFS 会无限循环；即使没有环，共享依赖也会被重复处理，导致计算和副作用执行多次。

“已发现”和“已完成”有时需要分开。拓扑排序和循环检测通常使用三种状态：未访问、正在访问、已完成。遍历一条边时如果遇到正在访问的节点，说明当前依赖链上存在环；遇到已完成节点则可以复用结果。

JavaScript
function dependencyFirstOrder(graph) {
  const state = new Map();
  const order = [];

  function visit(node) {
    const current = state.get(node) ?? 0;
    if (current === 1) throw new Error(`发现循环依赖：${node}`);
    if (current === 2) return;
    state.set(node, 1);
    for (const neighbor of graph.get(node) ?? []) visit(neighbor);
    state.set(node, 2);
    order.push(node);
  }

  for (const node of graph.keys()) visit(node);
  return order;
}

这里沿用开头的语义：graph.get(A) 是 A 依赖的节点。后序加入 order 已经让依赖先于使用者，所以不能再 reverse；若把边改定义为“必须先于”，才需要相反的输出方向。《如何用拓扑排序解析前端任务和模块依赖？》中的 orderByPrerequisites 用 Kahn 入度算法，输入同样是“节点 → 它的前置依赖”，两者结果都把依赖排在使用者之前，但同层节点的先后可能不同。

这个实现使用递归，适合示例规模；依赖图可能非常深时应改成显式栈，并在输入阶段限制规模。拓扑排序只适用于有向无环图，示例报出遇到回边的节点，但未构造完整环路径；生产诊断可增加当前路径记录。

复杂度和内存要按图的规模算

在常见 Map/Set 查询近似常数时间的实现假设下，邻接表 BFS/DFS 遍历耗时 O(V + E)，其中 V 是节点数，E 是边数。BFS 在入队时标记，每个节点最多入队一次，额外空间 O(V)。本例 DFS 则在出栈时标记：尚未访问的共享邻居可能被重复压栈，因此待处理栈最坏可达到 O(E)，不能无条件声称它只需 O(V) 空间。需要严格控制栈大小时，可改为保存遍历帧和邻居下标的实现。

示例假定节点 ID 是非空字符串、邻接表完整且遍历期间不修改。缺失起点的 DFS 返回 undefined，BFS 返回 null；缺失邻居不应默默当作合法外部节点，需在入口校验阶段拒绝或明确定义。邻接矩阵空间 O(V²)，不适合稀疏的大型依赖图。

实际前端还要计算解析后的节点对象、路径和缓存结果，不能只看算法复杂度就认为内存一定可接受。对用户上传的图、服务端返回的关系和可编辑流程，要限制深度、节点数、边数和单个 ID 大小。

异步图遍历不是把回调改成 async

如果遍历每个节点都要请求接口，直接在 DFS 中 await 会让执行顺序变成串行；把所有邻居都 Promise.all 又可能一次启动数千个请求。应明确并发上限、取消信号、失败策略和结果过期检查。

遍历依赖图时，某个节点失败是否阻止整个图、是否允许部分结果、重复节点是否共用进行中的 Promise，都属于业务协议。普通 BFS/DFS 只决定访问顺序，不自动提供网络重试、并发池或事务。

图遍历的实现质量不在于写出最短的递归函数，而在于边的方向、访问身份、环和失败语义都清楚。把这些约束写进数据结构和测试，才能让它服务于真实的路由、依赖和权限场景。

CP-Algorithms · Breadth-first search反馈此题