Jaki jest najbardziej wydajny algorytm i struktura danych do utrzymywania informacji o podłączonych komponentach na wykresie dynamicznym?

Powiedzmy, że mam niedokierowany skończony wykres rzadki i muszę być w stanie efektywnie uruchamiać następujące zapytania:

• $IsConnected(N_1, N_2)$ - zwraca jeśli istnieje ścieżka między i , w przeciwnym razie$T$$N_1$$N_2$$F$
• $ConnectedNodes(N)$ - zwraca zestaw węzłów, które są osiągalne z$N$

Można to łatwo zrobić przez wstępne obliczenie połączonych elementów wykresu. Oba zapytania mogą działać w czasie .$O(1)$

Jeśli muszę również móc dowolnie dodawać krawędzie - - wtedy mogę przechowywać komponenty w rozłącznej strukturze danych . Ilekroć dodawana jest krawędź, która łączy dwa węzły w różnych komponentach, scalałbym te komponenty. Dodaje to koszt do i do i (które równie dobrze mogą być ).$AddEdge(N_1, N_2)$$O(1)$$AddEdge$$O(InverseAckermann(|Nodes|))$$IsConnected$$ConnectedNodes$$O(1)$

Jeśli muszę również mieć możliwość arbitralnego usuwania krawędzi, jaka jest najlepsza struktura danych, aby poradzić sobie z tą sytuacją? Czy ktoś jest znany? Podsumowując, powinien skutecznie wspierać następujące operacje:

• $IsConnected(N_1, N_2)$ - zwraca , jeśli istnieje ścieżka między i , inaczej .$T$$N_1$$N_2$$F$
• $ConnectedNodes(N)$ - zwraca zestaw węzłów, które są dostępne z .$N$
• $AddEdge(N_1, N_2)$ - dodaje krawędź między dwoma węzłami. Pamiętaj, że , lub oba mogły wcześniej nie istnieć.$N_1$$N_2$
• $RemoveEdge(N_1, N_2)$ - usuwa istniejącą krawędź między dwoma węzłami.

(Interesuje mnie to z punktu widzenia rozwoju gry - ten problem wydaje się występować w kilku sytuacjach. Może gracz może budować linie energetyczne i musimy wiedzieć, czy generator jest podłączony do budynku. Może gracz może zablokować i odblokować drzwi, i musimy wiedzieć, czy wróg może dosięgnąć gracza. Ale to bardzo ogólny problem, więc sformułowałem to jako takie)

Problem ten nazywany jest łącznością dynamiczną i jest aktywnym obszarem badań w teoretycznej społeczności informatycznej. Nadal istnieją tutaj ważne problemy.

Aby wyjaśnić terminologię, poprosisz o w pełni dynamiczną łączność, ponieważ chcesz dodawać i usuwać krawędzie. Istnieje wynik Holm, de Lichtenberg i Thorup (J.ACM 2001), który osiąga czas aktualizacji i czas zapytania . Z mojego zrozumienia wydaje się to możliwe do wdrożenia. Mówiąc wprost, struktura danych utrzymuje hierarchię obejmującą drzewa - a dynamiczną łączność w drzewach łatwiej jest pokryć. Dla lepszego wyjaśnienia mogę polecić notatki Erika D. Demaine'a. Zobacz tutaj wideo. Notatka Erika zawiera także wskaźniki do innych istotnych wyników. Uwaga: wszystkie te wyniki są wynikami teoretycznymi.$O(\log^2 n)$$O(\log n / \log\log n)$

Te struktury danych mogą nie zapewniać samych zapytań ConnectedNodes , ale łatwo to osiągnąć. Po prostu utrzymuj jako dodatkową strukturę danych wykres (powiedzmy jako podwójnie połączoną listę krawędzi) i wykonaj najpierw wyszukiwanie głębokości, aby uzyskać węzły, do których można dotrzeć z określonego węzła.