Algorytm znajdowania wszystkich mostów jest całkiem prosty. Wystarczy bowiem odpowiednio zmodyfikować przeglądanie grafu w głąb (DFS).
Implementację algorytmu w C++ umieściłem w zasobach mojej RNO-Wiki, czyli tutaj: Znajdowanie mostów.
środa, 19 marca 2008
Mosty w grafie prostym (implementacja w C++)
Mostem w grafie nieskierowanym nazywamy każdą krawędź, której usunięcie powoduje zwiększenie liczby spójnych składowych. Na poniższym rysunku zaznaczyłem wszystkie mosty kolorem czewonym:
Algorytm znajdowania wszystkich mostów jest całkiem prosty. Wystarczy bowiem odpowiednio zmodyfikować przeglądanie grafu w głąb (DFS).
Implementację algorytmu w C++ umieściłem w zasobach mojej RNO-Wiki, czyli tutaj: Znajdowanie mostów.
Algorytm znajdowania wszystkich mostów jest całkiem prosty. Wystarczy bowiem odpowiednio zmodyfikować przeglądanie grafu w głąb (DFS).
Implementację algorytmu w C++ umieściłem w zasobach mojej RNO-Wiki, czyli tutaj: Znajdowanie mostów.
Subskrybuj:
Komentarze do posta (Atom)
4 komentarze:
Witam. Czy mógłbym prosić Pana o wyjaśnienie na czym polega ta modyfikacja DFS. Chodzi mi o taki opis słowny jak ten algorytm znajduje mosty, jak sprawdza czy dana krawędź jest mostem?
Proszę bardzo: http://www.astagor.net/putinf/data/algorytmy/Graf-2spojne.html
Podany przez Pana link już nie działa.
Dorzucam się więc do prośby o więcej komentarzy w kodzie źródłowym - co przechowuje dana tablica itp. (najlepiej by było, jakby Pan założył, że czytelnicy są idiotami - mogę nawet służyć za przykład).
Nie wiem czemu, ale już działa.
(ale sprawdzałem w 2 przeglądarkach wcześniej i nic)
Tak czy inaczej nadal nie miałbym nic przeciwko dod. komentarzom. ;-)
Prześlij komentarz