是否有支持高效编辑的 DAG 数据结构？
我正在寻找一种可以存储任何 DAG 的数据结构，但可以有效地（即，边/顶点数量呈次线性）检测添加边是否会创建循环（从而防止您破坏非循环不变量） ）。有谁知道这样的事情吗？
谢谢！
I'm looking for a data structure that will store any DAG, but can efficiently (i.e., sub-linearly in the number of edges/vertices) detect if adding an edge would create a cycle (and thus prevent you from breaking the acyclic invariant). Does anyone know of such a thing?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以维护有关图的传递闭包的数据结构。然后检查添加边是否会导致循环是在恒定时间内完成的；如果要添加边 (i,j)，请检查是否已经存在从 j 到 i 的路径。然而，更新数据结构一般来说成本可能更高（参见例如 La Poutré 和 van Leeuwen ）。
You could maintain a datastructure about the graph's transitive closure. Then checking whether adding an edge causes cycles is done in constant time; if you want to add edge (i,j), check if there is already a path from j to i. However, updating the datastructure could be more costly in general (see e.g. La Poutré and van Leeuwen).