Salesforce依赖树构建：求内存与速度更优的DAG生成算法

针对你遍历对象关系生成DAG的场景，Khan算法本身时间复杂度为O(V+E)，但确实存在在内存占用、实际运行速度上更优的替代方案，具体取决于你的数据特征：

1. 基于深度优先搜索（DFS）的拓扑排序 #

这是最常用的替代方案，核心逻辑是通过DFS遍历节点，将完成遍历的节点压入栈，最后反转栈得到拓扑序。

• 内存优势：无需维护Khan算法所需的入度表，仅需邻接表（或直接遍历对象关系）和访问状态标记（未访问/访问中/已访问）。对于稀疏的对象关系图，内存开销比Khan算法低——省去了存储每个节点入度的额外空间，递归栈或手动栈的内存开销通常也小于Khan的队列+入度表组合。
• 速度优势：实际运行中常数更低，没有频繁的入度更新和队列操作，尤其是对象关系呈现深度优先结构时，缓存友好性更好，遍历效率更高。
• 注意点：需要通过访问状态检测环（标记“访问中”的节点如果被再次访问，说明存在环），环检测复杂度与Khan算法一致。

2. 原地修改的拓扑排序（适用于可修改的对象结构） #

如果你的对象实例本身允许添加临时字段（比如in_degree或visited标记），可以直接在对象上存储状态，完全省去额外的辅助数据结构：

• 内存优势：仅需存储遍历所需的临时栈/队列，无需单独的入度表或状态数组，内存开销可降至O(E)（甚至更低，如果直接遍历对象关系而不提前构建邻接表）。
• 速度优势：避免了哈希表或数组的查找开销，直接操作对象本身的字段，遍历效率进一步提升。

3. 基于逆邻接表的拓扑排序（针对特定稀疏场景） #

如果你的对象关系中，大部分节点的出度极少（比如每个对象仅依赖少数父节点），可以改用逆邻接表存储每个节点的前驱关系：

• 内存优势：逆邻接表的存储空间比原邻接表更紧凑，减少了冗余存储。
• 速度优势：遍历过程中减少了入度更新的次数，批量处理节点时效率更高。

选择建议 #

• 若你的对象关系是稀疏图、深度较大：优先选DFS-based拓扑排序，内存和速度表现最优。
• 若对象允许原地修改：配合原地标记的方式，进一步压缩内存开销。
• 若你的场景需要动态添加节点或提前终止遍历：Khan算法的队列结构反而更灵活，此时无需替换。

内容的提问来源于stack exchange，提问作者srikanth suryadevara