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

我正在寻找一种数据结构，它将存储任何DAG，但可以有效地（即，在边数/顶点数中以子线性方式）检测添加边是否会创建一个循环（从而防止您打破非循环不变）。有人知道这样的事情吗？DAG是否有支持高效编辑的数据结构？

谢谢！

2011-10-25 copumpkin

本文[增量拓扑订购]（http://www.cs.princeton.edu/~sssix/papers/dto-conf.pdf）的更快算法，声称**摊销** O（m^1/2）每弧添加。不知道这是否足够好，或者是否可能出现最坏情况。我没有看过介绍。 – Crosbie

您可以维护一个关于该图的数据结构transitive closure。然后检查加边是否会导致循环在恒定时间内完成;如果你想添加边（i，j），检查是否有从j到i的路径。但是，更新数据结构一般可能更昂贵（参见例如La Poutré and van Leeuwen）。

2011-12-26 11:30:17 mitchus

回答