如何基于before/after规则实现dependency resolver并完成依赖排序

核心就是把所有前后置约束转换成有向图，靠拓扑排序生成合法的依赖执行顺序，同时通过环检测识别矛盾约束。

1. 先把所有before/after约束统一转成图的边 #

所有前后置约束的本质是等价的单向指向关系，转换规则非常好记：

• 只要定义了「X 必须排在 Y 前面」，就加一条从X指向Y的有向边，代表X是Y的前置
• 转的时候记得给重复的边去重，不然后面统计入度的时候会算错
  拿题目给的示例约束转完，完整的边集合是：
• A在B、C之前：加A→B、A→C
• A在D、E之后：反过来就是D、E都在A前面，加D→A、E→A
• D在E之前：加D→E
• E在Z之前：加E→Z
• E在Y之后：反过来是Y在E前面，加Y→E

2. 用Kahn算法做拓扑排序生成合法序列 #

Kahn算法是最适合依赖解析场景的拓扑排序实现，执行步骤：

• 先统计每个节点的入度：也就是有多少条边指向它，对应有多少个必须排在它前面的依赖
• 把所有入度为0的节点先丢进待处理队列——这类节点没有任何前置要求，是可以最先运行的
• 循环处理直到队列空：
  • 从队列里拿一个节点，直接放进最终的有序结果列表
  • 把这个节点所有指向的相邻节点的入度都减1，代表这个前置已经处理完了
  • 如果某个相邻节点的入度减到0了，说明它的所有前置都搞定了，就把它也丢进待处理队列
  • 队列里排队的节点之间没有先后约束，顺序可以随便换，只要不违反边的指向关系，出来的序列就是合法的
    拿题目里的示例算一遍，最后能生成的合法序列比如Y → D → E → A → Z → B → C，只要满足所有前置要求，同层级的节点换顺序不影响合法性。

3. 矛盾约束的失败判定逻辑 #

只要约束之间有逻辑冲突，最后一定会在图里形成闭环（也就是循环依赖），判定逻辑不需要搞复杂：

• 等Kahn算法跑完全部流程、队列空了之后，对比一下最终生成的有序列表长度，和你收集到的全量依赖节点总数
• 如果列表长度比总节点数少，说明剩下没处理的节点全在闭环里，它们的入度永远降不到0，直接判定约束矛盾、解析失败
  举个典型的矛盾例子：如果额外加一条约束「A必须排在D前面」，之前的约束已经有D→A的边了，现在加A→D就形成了D→A→D的死循环。这时候跑Kahn算法，D和A的入度永远没法降到0，最后生成的列表长度肯定比总节点数少，直接触发失败就行。

顺带提个边界处理：完全没有任何前后置约束的孤立依赖，入度天然是0，会被正常丢进待处理队列，不会漏算。

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