data-structures - DAG是否有支持有效编辑的数据结构？

Question

我正在寻找一种数据结构，该数据结构将存储任何DAG，但可以有效地(即，在边/顶点的数量上是次线性的)检测是否添加边会创建一个循环(从而防止破坏非循环不变式) )。有人知道这样的事吗？

谢谢!

Answer 1

您可以维护有关图的 transitive closure 的数据结构。然后检查是否增加边沿会导致循环，请在固定时间内完成；如果要添加边(i，j)，请检查是否存在从j到i的路径。但是，一般而言，更新数据结构的成本可能更高(请参见La Poutré and van Leeuwen)。