我很长时间对直接无环图（DAG）感兴趣，在阅读维基百科的拓扑排序之后，我没有发现任何涉及 layers numbering 的方法的特别提及（尽管图中广泛提到了绘图） . 使用这种方法，图形在技术上不是拓扑排序的，但是知道每个节点包含层（级别）的正确数字，我们总是可以判断特定节点"bigger"是否在拓扑上 . 另一方面，只要我们没有有序列表，我们就无法在拓扑上枚举节点（尽管这可以通过比较节点级别的最终传统排序来完成） .
该方法允许在保持级别信息的正确性的同时实现任意连接 . 步骤可以是：
-
对于任何新添加的节点（没有任何连接），应用的级别为1 .
-
如果请求两个节点之间的连接（从m到n）和n.level> m.level，那么它们只是简单地连接，不需要为其他节点修复级别 .
-
如果对于请求的连接（从m到n）n.level <= m.level然后我们将n.level更改为（m.level 1）并递归检查n的任何依赖关系以获得类似的级别增加（或者如果级别没有增加在递归步骤是兼容的） .
-
如果我们保留递归输入节点的列表，那么我们可以检测到循环并实现某种撤销操作的尝试（将所有受影响节点的级别返回到先前的值）
对于它们之间的任何已知节点和连接集合，我们只需添加应用level = 1的所有节点，并尝试应用（忽略和撤消cicles）之间的所有已知连接 .
最终级别信息不仅允许在拓扑上比较节点，还包含其他有用信息 . 例如：
-
level = 1的每个节点都没有传入连接（每个路径都从其中一个开始） . 因此任何DAG枚举都可以从它们开始 .
-
最长路径（边数）不能长于（最大等级1）
我想对于一些人工数据（n个节点，每个Node（n）连接到Node（n 1）），这个算法可能非常慢 . 但对于真实世界的数据，我尝试了它（维基百科类别 - 800,000个节点 - 2,000,000个连接）时间合适（5-10分钟），水平和周期尝试次数很少（369级，1000次循环尝试）
这个方法是新的还是众所周知的，但是在维基百科和其他资源中没有广泛呈现？既然它不是一种（技术上），它应该被称为数据重组吗？
3 回答
考虑一个DAG，它由两个"parallel"定向路径组成，它们共享起始节点和最后一个节点
n. 此处的层编号比拓扑顺序更具限制性 . 在拓扑顺序中，即使其层数较大，您也可以在路径B的第二个节点之前从路径A放置倒数第二个节点 .可能有人之前已经想过这个，但由于最坏的情况是线性的，我很难指出你所描述的研究文章 . 此算法解决的问题的名称是“增量拓扑排序”（或动态，其中边缘删除也是可能的） .
有一些论文关于逐步维护图中节点的拓扑顺序，并对您描述的算法进行了变化 .
如果图形具有
n个节点和m边缘，则每次插入边缘时都会花费时间O(m + n). 论文询问插入k边需要多长时间？琐碎的，O(k * (n + m)). 但实际上你可以显示更好的上界 - 像O(k * sqrt(m + n))足够大k.下面的一些链接还有更多：
http://igitur-archive.library.uu.nl/math/2007-0725-201647/2005-011.pdf
http://arxiv.org/abs/0802.1059
http://www.siam.org/proceedings/soda/2009/SODA09_120_benderm.pdf