Ich versuche ein Grafikproblem zu lösen (es ist nicht für Hausaufgaben gedacht, nur um meine Fähigkeiten zu üben). Ein DAG ist gegeben, wobei die Menge der Eckpunkte und die Kanten ist. Das Diagramm wird als Adjazenzliste dargestellt, daher ist eine Menge, die alle Verbindungen von . Meine Aufgabe ist es, zu finden, welche Eckpunkte von jedem Eckpunkt . Die Lösung, die ich benutze, hat eine Komplexität von mit transitivem Abschluss, aber ich habe gelesen, dass es in einem Blog schneller sein kann, obwohl es nicht verriet, wie. Könnte mir jemand einen anderen Weg (mit besserer Komplexität) zur Lösung des Transitivverschlussproblems in einer DAG nennen?
algorithms
graph-theory
graphs
Rontogiannis Aristofanis
quelle
quelle
Antworten:
Die Tatsache, dass unser Graph azyklisch ist, macht dieses Problem viel einfacher.
Topologische Sortierung kann uns eine Reihenfolge der Eckpunkte so dass, wenn i < j ist , es keine Kante von v j zurück zu v i gibt . Wir haben die Eckpunkte so aufgelistet, dass alle Kanten in unserer Liste "vorwärts" gehen.v1,v2,…,vn i<j vj vi
(bearbeitet, um die Analyse zu korrigieren und einen etwas schnelleren Algorithmus zu liefern)
Jetzt gehen wir diese Liste einfach rückwärts durch, beginnend mit dem letzten Scheitelpunkt . v n 's transitiver Abschluss ist nur sich selbst. Addiere auch v n zum transitiven Abschluss jedes Scheitelpunkts mit einer Kante zu v n .vn vn vn vn
Für jeden anderen Eckpunkt , das Ende nach hinten gehen, ersten Add v i auf seine eigenen transitiven Schließung, dann ist alles in der transitiven Hülle hinzufügen v i auf die transitive Schließung aller Ecken mit Ecken und Kanten v i .vi vi vi vi
Die Laufzeit ist im ungünstigsten Fall , wobei n die Anzahl der Eckpunkte und m ∈ O ( n 2 ) die Anzahl der Kanten ist. Die topologische Sortierung benötigt die Zeit O ( n + m ) . Dann machen wir eine weitere O ( m n ) -Arbeit im Rückwärtsdurchlauf: Wenn wir die Liste rückwärts durchgehen, müssen wir für jede Kante n addierenO(n+m+nm)=O(n3) n m∈O(n2) O(n+m) O(mn) n Eckpunkte zu jemandes transitiven Schließung.
Beachten Sie, dass Sie eine schöne Beschleunigung des konstanten Faktors erzielen können, indem Sie die transitive Schließung aller durch Bit-Arrays darstellen. Angenommen, Sie hatten nur ; Dann würden Sie eine einzelne 64-Bit-Ganzzahl verwenden, wobei Bit i 1 ist, wenn ich in meinem transitiven Abschluss bin, und sonst 0. Dann ist der Teil, in dem wir alles in i 's transitiven Abschluss zu j ' s hinzufügen, sehr schnell: Wir nehmen einfach c j | = c i . (Binär-ODER-Operation.)n=64 i i i j cj ci
Für müssten Sie sie in Arrays belassen und ein wenig rechnen, aber es wäre viel schneller als ein Objektsatz.n>64
quelle