Powiedzmy, że mam niedokierowany skończony wykres rzadki i muszę być w stanie efektywnie uruchamiać następujące zapytania:
- - zwraca jeśli istnieje ścieżka między i , w przeciwnym razie
- - zwraca zestaw węzłów, które są osiągalne z
Można to łatwo zrobić przez wstępne obliczenie połączonych elementów wykresu. Oba zapytania mogą działać w czasie .
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ć ).
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:
- - zwraca , jeśli istnieje ścieżka między i , inaczej .
- - zwraca zestaw węzłów, które są dostępne z .
- - dodaje krawędź między dwoma węzłami. Pamiętaj, że , lub oba mogły wcześniej nie istnieć.
- - 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)
źródło
Odpowiedzi:
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(log2n) O(logn/loglogn)
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.
źródło