Posługiwanie się rozłączną strukturą danych można łatwo połączyć z komponentem wykresu. I obsługuje tylko Incremental Connected Components.dynamiczne odnajdywanie podłączonego komponentu
Jednak w moim przypadku, usuwanie krawędzi jest bardzo często tak, że szukam algorytmu lub nowej struktury może utrzymać podłączonych urządzeń pełni dynamicznie (w tym dodawanie i usuwanie krawędzi)
Dzięki
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (Holm, de Lichtenberg and Thorup 2001) podaje algorytm, który pozwala na dowolną sekwencję wstawień krawędzi, delecji i zapytań o łączność, z aktualizacjami (wstawienia i usunięcia) pobierającymi O (log (n)^2) czas amortyzacji i zapytaniami przyjmującymi O (log (n)/log (log (n))), przy czym n oznacza liczbę wierzchołków na wykresie. Te granice czasowe zakładają, że wykres zaczyna się bez żadnych krawędzi.
Przeszukałem tylko pierwsze 2 z 38 stron, ale nie przejmuj się - w artykule opisano kilka nowych algorytmów na dynamicznych wykresach (czyli wykresy, które można skutecznie zmodyfikować czas), z których łączność jest najprostsza.
[Artykuł w Wikipedii] (http://en.wikipedia.org/wiki/Connected_component_ (graph_theory)) ma odniesienie. –
@ n.m. Który? "Niekierowana łączność w przestrzeni logu"? – Chang
"Problem z usunięciem krawędzi w linii" –