ś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.
Prześlij komentarz