咨询无权有向无环图最小长度分阶段拓扑排序算法及问题命名

你描述的需求是图论领域的经典问题，存在成熟的高效解法，其正式名称为最小层数拓扑分层，部分并行计算文献也将其结果称为DAG的正则层级划分，核心目标就是在严格满足拓扑序约束的前提下，将节点列表的分层长度压缩到理论最小值。
这个问题存在明确的理论下界：最小可能的分层长度，恰好等于输入DAG中最长有向路径（关键路径）所包含的节点总数。因为路径上的所有节点都存在前后依赖，必须被拆分到不同的分层中，不可能再做无冲突的压缩。

该问题的求解可以用线性复杂度的算法完成，核心逻辑是基于节点的最长入向路径长度做分层，步骤如下：

• 第一步：对输入DAG完成基础拓扑排序，得到节点的线性遍历顺序
• 第二步：按拓扑序递推计算每个节点的最长入向路径长度（即从任意入度为0的源点出发，到达当前节点的最长路径包含的节点数）：
  • 初始阶段，所有入度为0的源点，路径长度值设为1
  • 遍历到节点u时，逐一更新u的所有直接后继节点v的路径长度：取v当前已有长度值，和u的长度值 + 1两者的最大值，作为v的最终长度
• 第三步：将所有路径长度值相同的节点归为同一个集合，再按集合的路径长度值从小到大排序，最终得到的列表就是满足要求的最小长度分层结果

这种方式生成的分层一定满足两个约束要求：

1. 拓扑序约束：对于任意边u->v，v的路径长度一定严格大于u的路径长度，因此v所在的集合位置必然在u的集合之后，完全符合拓扑序要求
2. 长度最小约束：分层的总层数等于所有节点路径长度的最大值，也就是DAG关键路径的节点数，和之前提到的理论下界完全对齐，不存在更短的合法分层方案

对应你给出的示例场景，用该算法得到的分层结果为[1], [2, 3], [4, 5], [6, 7]，总长度为4层，就是理论可达到的最小值。你提到的另一种结果[1], [2, 3], [4], [5, 6, 7]虽然满足拓扑序约束，但总层数同样是4层，属于同最优长度下的不同节点组合，没有实现长度的进一步压缩。

该算法整体时间复杂度为O(V+E)，和基础拓扑排序复杂度一致，适合处理大规模DAG场景。

内容的提问来源于stack exchange，提问作者Mo B.