动态图并不是把静态图全部推翻重来，而是在保留邻接查询效率的同时，为每次拓扑变化建立可追踪的版本。Node.js 的单线程事件循环非常适合处理高频、小批量的图更新，只要内存结构设计得当，就能在不引入外部图数据库的前提下获得不错的实时性。本文实现的 DynamicGraph 使用 Map 加 Set 作为基础容器，所有方法都围绕当前版本和操作日志展开，方便后续做增量查询、快照回溯和批量操作。

一、为什么动态图需要邻接表加版本号

动态图最直接的需求是节点和边可以随时变化。如果用邻接矩阵存储，新增一个节点意味着矩阵需要整体扩容，删除一个节点还会留下大量无效位置。邻接表则不同，它只保存实际存在的边，配合 JavaScript 的 Map 和 Set，可以在常数时间内完成大部分增删和存在性判断。在 DynamicGraph 中，每个节点对应 Map 中的一个键，值是用 Set 维护的出边集合，这种结构尤其适合边稀疏但节点频繁变化的场景。

仅有可变结构还不够。当图发生变更时，调用方往往需要知道当前处于哪个版本，或者把图恢复到某个历史状态。因此每个变更操作都会触发一次 commit，版本号自增并写入操作日志。日志记录的不只是结果，还包括操作类型和操作对象，这样后续就可以通过重放日志来重建指定版本，或者审计某条边是何时被添加的。

class DynamicGraph {
  constructor() {
    this.adj = new Map();
    this.version = 0;
    this.log = [];
  }
  hasNode(id) {
    return this.adj.has(id);
  }
  addNode(id) {
    if (this.hasNode(id)) return false;
    this.adj.set(id, new Set());
    this.commit({ type: 'addNode', id: id });
    return true;
  }
  commit(operation) {
    this.version += 1;
    this.log.push({
      version: this.version,
      time: Date.now(),
      op: operation
    });
  }
}

上面这段代码搭建了 DynamicGraph 的基础骨架。commit 方法统一处理版本递增和日志追加，避免在 addNode、addEdge 等方法中重复编写状态记录逻辑。这样做还有一个好处：如果未来需要接入事件监听或 WebSocket 推送，只需要在 commit 里增加通知逻辑，所有变更都会自动携带版本信息。

二、节点与边的增量更新：处理级联和脏数据

添加边之前必须先确认两个节点存在，否则邻接表里会出现悬空引用。removeNode 则更复杂，因为一个节点可能被多条边指向，如果只删除节点本身而不清理入边，后续遍历时就会拿到指向不存在节点的脏数据。下面这段代码把添加边、删除边和删除节点放在一起，重点展示级联清理逻辑。

addEdge(from, to) {
  if (!this.hasNode(from) || !this.hasNode(to)) {
    throw new Error('Both nodes must exist before adding an edge');
  }
  const targets = this.adj.get(from);
  if (targets.has(to)) return false;
  targets.add(to);
  this.commit({ type: 'addEdge', from: from, to: to });
  return true;
}
removeEdge(from, to) {
  const targets = this.adj.get(from);
  if (!targets || !targets.has(to)) return false;
  targets.delete(to);
  this.commit({ type: 'removeEdge', from: from, to: to });
  return true;
}
removeNode(id) {
  if (!this.hasNode(id)) return false;
  this.adj.delete(id);
  for (const [from, targets] of this.adj) {
    if (targets.has(id)) {
      targets.delete(id);
      this.commit({ type: 'removeEdge', from: from, to: id });
    }
  }
  this.commit({ type: 'removeNode', id: id });
  return true;
}

removeNode 首先删除该节点的出边集合，然后遍历每个源节点的 Set，检查其中是否包含被删除节点的标识。如果存在，就删除这条入边并记录一次 removeEdge 操作。这种做法的优点是实现直观，缺点是删除节点时需要扫描全部邻接关系，复杂度接近 O(V + E)。当节点数量很大时，可以额外维护一个入边索引，例如用另一个 Map 记录每个节点被哪些源节点引用，这样删除节点时就能直接定位到关联边，避免全量扫描。

另一个容易忽视的问题是重复操作。addEdge 会先判断目标边是否已存在，如果存在就直接返回 false，不产生新版本；removeEdge 同理，找不到对应边时不提交日志。这种幂等设计对动态图非常重要，因为实时事件经常会出现重复推送，如果每次重复事件都生成新版本，日志会迅速膨胀，快照和回滚也会变得不可靠。

三、时间快照与回溯：全量快照还是增量日志

快照是动态图实现中争议最大的部分。最简单的方式是在某个时刻把当前邻接表完整复制一份，调用方可以脱离原图自由读取。这种全量快照读取速度快，但内存开销会随着图规模线性增长，不适合高频快照。DynamicGraph 选择增量日志与按需重建相结合，snapshot 方法生成只读性的当前拓扑副本，rollback 方法则利用日志重建目标版本。

snapshot() {
  const nodes = Array.from(this.adj.keys());
  const edges = [];
  for (const [from, targets] of this.adj) {
    for (const to of targets) {
      edges.push({ from: from, to: to });
    }
  }
  return {
    version: this.version,
    nodes: nodes,
    edges: edges,
    time: Date.now()
  };
}
rollback(targetVersion) {
  if (targetVersion < 0 || targetVersion > this.version) {
    throw new Error('Invalid target version');
  }
  const graph = new DynamicGraph();
  for (const record of this.log) {
    if (record.version > targetVersion) break;
    graph.applyRecord(record.op);
  }
  return graph;
}
applyRecord(op) {
  if (op.type === 'addNode') this.addNode(op.id);
  if (op.type === 'addEdge') this.addEdge(op.from, op.to);
  if (op.type === 'removeEdge') this.removeEdge(op.from, op.to);
  if (op.type === 'removeNode') this.removeNode(op.id);
}

snapshot 的输出包含版本号、节点列表、边列表和时间戳，可以序列化成 JSON 后落盘或发送给前端。对于需要历史对比的场景，rollback 会从空图开始，按日志顺序重放直到目标版本。如果目标版本是 0，返回的就是没有任何节点和边的初始图。如果目标版本等于当前版本，它和直接调用当前图对象得到的结果一致，但消耗了额外的重建时间。

增量重放的问题在于随着日志增长，回滚会越来越慢。一个实用的优化是混合策略：每隔若干次操作生成一次全量快照并保存，回滚时先找到目标版本之前最近的全量快照，再从这个快照开始重放少量增量日志。这样既避免了每次操作都复制全图，也防止日志过长导致回溯性能下降。对于节点数在几千到几万之间的服务端图模型，这个策略通常能在内存和延迟之间取得很好的平衡。

四、一致性与性能的平衡

Node.js 的单线程模型让 DynamicGraph 天然避免了多线程写入冲突，但异步回调仍然可能带来顺序问题。比如两个事件同时到达，A 事件添加节点，B 事件添加以该节点为终点的边，如果 B 先执行就会抛错。解决这个问题一般有两种方式：一是在上游把事件排队，二是提供批量接口，让多个操作按照数组顺序一次性提交。批量接口还能让调用方把一组相关变更视为一个逻辑单元，减少中间状态被外部观测到的概率。

batch(operations) {
  const backups = [];
  for (const op of operations) {
    backups.push(this.snapshot());
    this.applyRecord(op);
  }
  return backups;
}

batch 方法会按顺序执行 operations 中的每个操作，并返回每次执行前的快照备份。这些备份可以用于自定义回滚，例如当批量任务中途失败时，调用方可以用返回的备份依次恢复。虽然这增加了内存占用，但对于批量导入、定时同步等一次性任务来说非常实用。如果批量操作很大，也可以把内部备份改为只记录受影响范围的差异数据，而不是整份快照。

动态图的性能最终取决于节点规模、变更频率和快照频次。邻接表在稀疏图里表现很好，但如果图越来越稠密，Set 之间的遍历和删除开销会上升。此时可以考虑把出边集合替换成不可变结构，或者使用分片 Map 降低单次扫描范围。对于大多数实时监控、依赖分析、社交关系同步等场景，本文实现的 DynamicGraph 已经足够轻量且容易扩展。关键是让每一次变更都有版本可查，让旧的拓扑不会因为新数据的到来而彻底丢失。