cop*_*kin 9 graph cycle directed-acyclic-graphs data-structures
我正在寻找一种能够存储任何DAG的数据结构,但是能够有效地(即,在边/顶点的数量中进行次线性)检测是否添加边缘会创建一个循环(从而防止您破坏非循环不变量) ).有谁知道这样的事情？
谢谢!
您可以维护有关图的传递闭包的数据结构。然后检查添加边是否会导致循环是在恒定时间内完成的；如果要添加边 (i,j)，请检查是否已经存在从 j 到 i 的路径。然而，更新数据结构通常可能成本更高（参见例如La Poutr\xc3\xa9 和 van Leeuwen）。
\n