operacja odwrotna do "Unii i znajdź"

Wiemy, że istnieje "Unia i znajdź" dla zbiorów rozłącznych. http://en.wikipedia.org/wiki/Union_find operacja odwrotna do "Unii i znajdź"

Ale jak wykonać odwrotną operację? Rozważmy zestaw z N węzłami połączonymi z krawędziami E (który jest w rzeczywistości wykresem). I na każdym kroku chcemy usunąć pewną krawędź i sprawdzić, czy ta operacja usuwania prowadzi do kolejnego rozłącznego zestawu. Czy można to zrobić szybko, jak w "Unii i znaleźć"?

P.S to nie jest zadanie domowe, mamy wakacje :)

Źródło

2011-06-22 Spinach

ten jest znany jako internetowym problemu delecji krawędź lub problemu z połączeniem internetowym. Niektóre linki do algorytmów są w tym section of the Wikipedia article on graph connectivity.

Źródło

2011-06-22 10:24:52

Dzięki za link. Mogę znaleźć tylko artykuły do kupienia na ACM. Nie można znaleźć żadnych informacji na temat TopCoder, żadnego bezpośredniego linku? :) – Spinach

Więc twoje pytanie brzmi, jak skutecznie wykryć Bridge? Można to zrobić w czasie liniowym (zobacz także link).

Źródło

2011-06-22 10:25:43 dcn

Biorąc pod uwagę, że @Chris najwyraźniej chce wykonywać tę operację wielokrotnie (mówi "przy każdym kroku"), możemy być bardziej skuteczni, jeśli chodzi o wykrywanie mostów na każdym etapie. – borrible

Myślę, że jeśli uruchomisz ten algorytm znajdowania mostów i zaznaczysz mosty i zauważysz, że jeśli do wykresu nie zostanie dodana krawędź, nie pojawią się żadne nowe mosty; wszystkie mosty, które istnieją na tym wykresie, pozostają mostami, ponieważ krawędzie są usuwane, a nowe mosty mogą się pojawiać tylko wtedy, gdy usuniesz krawędź, która nie jest mostem; więc wystarczy ponownie uruchomić algorytm na dwóch podgraphach, które zostały połączone przez niezmostowaną krawędź, która właśnie została usunięta. –

Funkcja wyszukiwania odniesień jest używana w algorytmie Kruskala, który wielokrotnie dodaje krawędź minimalnej masy, która nie tworzy cyklu. Odwrotna idea - usuwanie krawędzi o maksymalnej wadze, o ile nie rozłącza wykresu - jest używana w reverse-delete algorithm, która pozornie może wykorzystywać jakąś skomplikowaną strukturę danych (patrz Wikipedia).

Źródło

2011-06-22 11:29:03 sdcvvc

Następny fajny link, ale za dużo uogólniony i nie ma kodu do obejrzenia :( – Spinach

operacja odwrotna do "Unii i znajdź"

Odpowiedz

Powiązane problemy