data-structures - 効率的な編集をサポートするDAGのデータ構造はありますか？

Question

DAGを格納するデータ構造を探していますが、エッジを追加するとサイクルが作成されるかどうかを効率的に（つまり、エッジ/頂点の数でサブリニアに）検出できます（したがって、非循環不変量を壊すことを防ぐことができます） ）。誰かがそのようなことを知っていますか？

ありがとう！

Answer 1

グラフの推移閉包に関するデータ構造を維持できます。次に、エッジを追加するとサイクルが発生するかどうかのチェックが一定時間で行われます。エッジ（i、j）を追加する場合は、jからiへのパスがすでに存在するかどうかを確認します。ただし、データ構造の更新は、一般的にコストがかかる可能性があります（たとえば、LaPoutréおよびvan Leeuwenを参照）。