我正在寻找一种数据结构，该数据结构将存储任何DAG，但可以有效地(即，在边/顶点的数量上是次线性的)检测是否添加边会创建一个循环(从而防止破坏非循环不变式) )。有人知道这样的事吗？
谢谢!
最佳答案
您可以维护有关图的 transitive closure 的数据结构。然后检查是否增加边沿会导致循环，请在固定时间内完成；如果要添加边(i，j)，请检查是否存在从j到i的路径。但是，一般而言，更新数据结构的成本可能更高(请参见La Poutré and van Leeuwen)。
关于data-structures - DAG是否有支持有效编辑的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7893520/