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

9

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

  • IsConnected(N1,N2) - zwraca jeśli istnieje ścieżka między i , w przeciwnym razieTN1N2F
  • ConnectedNodes(N) - zwraca zestaw węzłów, które są osiągalne zN

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(N1,N2)O(1)AddEdgeO(InverseAckermann(|Nodes|))IsConnectedConnectedNodesO(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(N1,N2) - zwraca , jeśli istnieje ścieżka między i , inaczej .TN1N2F
  • ConnectedNodes(N) - zwraca zestaw węzłów, które są dostępne z .N
  • AddEdge(N1,N2) - dodaje krawędź między dwoma węzłami. Pamiętaj, że , lub oba mogły wcześniej nie istnieć.N1N2
  • RemoveEdge(N1,N2) - 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)

użytkownik253751
źródło
ConnectedNodes nie mógłby działać w , ponieważ jeśli zwróci listę węzłów, będzie potrzebował czasu. Implementacja z BFS jest optymalna, więc potencjalna struktura danych musiałaby obsługiwać tylko IsConnected, AddEdge i RemoveEdge. Wydaje się, że ma to znaczenie dla twojego pytania: stackoverflow.com/questions/7241151/...O(1)nΩ(n)ConnectedNodes
Tom van der Zanden
@TomvanderZanden Zwracanie zestawu, który jest już zbudowany (w programowaniu, wskaźnik lub odniesienie) to ... chociaż niewiele użytkowników może zrobić i nie jest objętych . O(1)ConnectedNodesO(1)IsConnected
user253751,

Odpowiedzi:

11

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.

A.Schulz
źródło