Was ist der effizienteste Algorithmus und die effizienteste Datenstruktur zum Verwalten der Informationen zu verbundenen Komponenten in einem dynamischen Diagramm?

Angenommen, ich habe ein ungerichtetes Diagramm mit endlicher Dichte und muss in der Lage sein, die folgenden Abfragen effizient auszuführen:

• $IsConnected(N_1, N_2)$ - gibt wenn zwischen und ein Pfad besteht , andernfallsN 1 N 2$T$$N_1$$N_2$$F$
• $ConnectedNodes(N)$ - Gibt die Menge der Knoten zurück, die von aus erreichbar sind$N$

Dies ist einfach durch Vorberechnung der verbundenen Komponenten des Diagramms möglich. Beide Abfragen können in -Zeit ausgeführt werden.$O(1)$

Wenn ich auch willkürlich Kanten hinzufügen muss - -, kann ich die Komponenten in einer disjunkten Datensatzstruktur speichern . Wenn eine Kante hinzugefügt wird und zwei Knoten in verschiedenen Komponenten verbunden werden, werden diese Komponenten zusammengeführt. Dies addiert Kosten zu und Kosten zu und (die genauso gut O (1) sein können ).$AddEdge(N_1, N_2)$A D d E d g e O ( I n v e r s e A c k e r m a n n ( | N o d e s | ) ) I s C o n n e c t e d C o n n e c t e d N $O(1)$$AddEdge$$O(InverseAckermann(|Nodes|))$$IsConnected$O ( 1 $ConnectedNodes$$O(1)$

Wenn ich auch in der Lage sein muss, Kanten willkürlich zu entfernen, welche Datenstruktur ist für diese Situation am besten geeignet? Ist man bekannt? Zusammenfassend sollte es die folgenden Operationen effizient unterstützen:

• $IsConnected(N_1, N_2)$ - liefert $T$ , wenn es einen Weg zwischen ist $N_1$ und $N_2$ , sonst $F$ .
• $ConnectedNodes(N)$ - Gibt die Menge der Knoten zurück, die von N aus erreichbar sind $N$.
• $AddEdge(N_1, N_2)$ - Fügt eine Kante zwischen zwei Knoten hinzu. Beachten Sie, dass $N_1$ , $N_2$ oder beide möglicherweise noch nicht vorhanden waren.
• $RemoveEdge(N_1, N_2)$ - Entfernt eine vorhandene Kante zwischen zwei Knoten.

(Ich interessiere mich aus der Perspektive der Spieleentwicklung dafür - dieses Problem scheint in einigen Situationen aufzutreten. Vielleicht kann der Spieler Stromleitungen bauen und wir müssen wissen, ob ein Generator an ein Gebäude angeschlossen ist. Vielleicht kann der Spieler sperren und Türen aufschließen, und wir müssen wissen, ob ein Feind den Spieler erreichen kann. Aber es ist ein sehr allgemeines Problem, also habe ich es als solches formuliert.

Dieses Problem ist als dynamische Konnektivität bekannt und ein aktives Forschungsgebiet in der theoretischen Informatik. Hier sind noch einige wichtige Probleme offen.

Um die Terminologie klar zu machen, fragen Sie nach einer volldynamischen Konnektivität, da Sie Kanten hinzufügen und löschen möchten. Es gibt ein Ergebnis von Holm, de Lichtenberg und Thorup (J.ACM 2001), das die Aktualisierungszeit und die Abfragezeit . Nach meinem Verständnis scheint es umsetzbar zu sein. Einfach ausgedrückt, die Datenstruktur behält eine Hierarchie von Spannbäumen bei - und die dynamische Konnektivität in Bäumen ist einfacher abzudecken. Ich kann Erik D. Demaines Notizen für eine gute Erklärung empfehlen, siehe hier für ein Video. Eriks Notiz enthält auch Hinweise auf andere relevante Ergebnisse. Hinweis: Alle diese Ergebnisse sind theoretische Ergebnisse.O ( log n / log log n $O(\log^2 n)$$O(\log n / \log\log n)$

Diese Datenstrukturen stellen möglicherweise keine ConnectedNodes- Abfragen per se bereit , dies ist jedoch einfach zu erreichen. Behalten Sie einfach als zusätzliche Datenstruktur den Graphen bei (z. B. als doppelt verbundene Kantenliste) und führen Sie die Tiefensuche durch, um die Knoten zu erhalten, die von einem bestimmten Knoten aus erreicht werden können.