Web Worker维护DAG与拓扑排序技巧

本文深入探讨了如何利用 Web Worker 高效处理有向无环图（DAG）的构建、动态更新与拓扑排序——将图结构管理（纯对象+邻接表表示）、Kahn 算法实现及增删边/节点等操作完全移入 Worker，避免主线程阻塞；通过预缓存入度、时间戳防重渲染、JSON-safe 消息通信和轻量错误协议，兼顾性能、可靠性和工程实用性，为前端复杂依赖调度、可视化编排、构建系统等场景提供了可落地的高性能解决方案。

Web Worker 适合处理 DAG 构建、更新和拓扑排序这类计算密集型任务，避免阻塞主线程。核心在于将图结构管理与排序逻辑完全移入 Worker，通过消息机制与主线程通信，同时注意数据结构的序列化限制和性能优化点。

Worker 中高效表示 DAG

不能直接传递 class 实例或函数，推荐用纯对象 + 邻接表（或逆邻接表）表示图：

• 顶点用唯一字符串或数字 ID（如 "task-login" 或 101）；
• 边用数组形式存储：例如 { edges: [["A", "B"], ["A", "C"], ["B", "D"]] }；
• 预计算并缓存每个节点的入度（indegree: { "A": 0, "B": 1, "C": 1, "D": 1 } ），避免每次排序都遍历全图；
• 若需频繁查依赖/被依赖关系，可额外维护 graph: { "A": ["B","C"], "B": ["D"] } 和 reverseGraph: { "B": ["A"], "C": ["A"], "D": ["B"] }。

在 Worker 中实现 Kahn 算法（推荐）

Kahn 算法天然适合 Worker 场景：迭代清晰、无递归栈风险、易于中断与增量更新：

• 初始化队列，放入所有入度为 0 的节点；
• 逐个取出节点，加入结果数组，并将其所有后继节点入度减 1；
• 若某后继入度降为 0，立即入队；
• 结束时检查结果长度是否等于节点总数——不等说明存在环，需向主线程报错。

注意：整个过程不操作 DOM，只做纯计算；可对超大图分批处理（如每 5000 步 postMessage 一次进度），但通常一次完成更高效。

支持动态图更新与重排序

真实业务中 DAG 常被增删边或节点（如添加新构建步骤、禁用某个模块）。Worker 可暴露以下能力：

• addEdge(from, to)：更新邻接表、to 的入度 +1；
• removeEdge(from, to)：反向操作；
• removeNode(id)：清除其所有出入边，并从入度/出度映射中删除；
• 每次变更后，调用一次拓扑排序并返回新序列——无需重建整个图，只需局部修正状态。

主线程只需发送操作指令（如 { type: "addEdge", from: "build", to: "test" }），Worker 执行并返回完整新拓扑序或错误信息。

与主线程通信注意事项

Worker 与主线程之间只能传递可序列化值（JSON-safe），不可传函数、Map/Set、Date 等：

• 图数据统一用 plain object + array 表示；
• 排序结果传回时，建议附带版本号或时间戳（如 { seq: ["A","B","C"], timestamp: 1747739700123 }），防止 UI 渲染旧结果；
• 若需高频率更新（如每秒多次依赖变更），可启用 Transferable（如 ArrayBuffer）提升大数据量传输效率，但对普通 DAG 通常不必要；
• 错误统一用 error: true + message 字段标识，便于主线程 toast 提示或降级处理。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Web Worker维护DAG与拓扑排序技巧》文章吧，也可关注golang学习网公众号了解相关技术文章。