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

Question

我正在寻找一种可以存储任何 DAG 的数据结构，但可以有效地（即，在边/顶点的数量上以次线性方式）检测添加边是否会产生循环（从而防止您破坏非循环不变量）。有谁知道这样的事情？

谢谢！

Answer 1

您可以维护有关图的传递闭包的数据结构。然后检查添加边是否导致循环是在恒定时间内完成的；如果要添加边 (i,j)，请检查是否已经存在从 j 到 i 的路径。然而，更新数据结构的成本通常会更高（参见例如La Poutré 和 van Leeuwen）。