Ich suche nach einer Datenstruktur, die alle DAG speichert, aber effizient (dh sublinear in der Anzahl der Kanten / Scheitelpunkte) erkennen kann, ob das Hinzufügen einer Kante einen Zyklus erzeugen würde (und somit einen Bruch verhindern würde) die azyklische Invariante). Weiß jemand so etwas?
Danke!
Sie können eine Datenstruktur über die transitive Schließung des Diagramms verwalten. Dann wird geprüft, ob das Hinzufügen einer Flanke Zyklen verursacht, und zwar in konstanter Zeit; Wenn Sie die Kante (i, j) hinzufügen möchten, prüfen Sie, ob bereits ein Pfad von j nach i vorhanden ist. Die Aktualisierung der Datenstruktur könnte jedoch generell kostspieliger sein (siehe z. B. La Poutré und van Leeuwen ). .
Tags und Links data-structures graph directed-acyclic-graphs cycle