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

回答