Przeszukiwanie grafu w głąb (DFS)
01.10.2010 - Michał Karpiński
Pseudokod - pierwsza przymiarkaNadszedł czas, aby zebrać wszystkie informacje, których dowiedzieliśmy się do tej pory o przeszukiwaniu w głąb i zapisaniu ich w prostej i czytelnej postaci. Skorzystamy ze sposobu zapisu algorytmów zwanego pseudokodem. Ta metoda jest bardzo przydatna i często stosowana w świecie informatyki, gdyż struktura pseudokodu przypomina kod języka programowania, ale pomija szczegóły implementacyjne (takie jak alokacja pamięci, deklaracja zmiennych). Nie ważne jaki jest nasz ulubiony język programowania. Wystarczy, że wiemy jak zapisać algorytm w pseudokodzie i na podstawie tej informacji będziemy w stanie przepisać algorytm do każdego znanego nam języka programowania. Na początek zdefiniujmy podstawowe struktury, którymi będziemy się posługiwali podczas pisania algorytmu:
Algorytm przeszukiwania w głąb składa się z dwóch procedur: Przeanalizujmy dokładnie, co dzieje się po uruchomieniu procedury DFS na dowolnym grafie G:
Oczywiście samo chodzenie po grafie i kolorowanie wierzchołków nas nie satysfakcjonuje. Powyższa wersja procedury DFS jest jedynie „szkieletem”, który w łatwy sposób można rozszerzyć. Dla przykładu: wierzchołek może zawierać o wiele więcej informacji niż tylko swój kolor (który i tak pełni jedynie rolę pomocniczą) np. w drzewie genealogicznym, jeśli każdą osobę przyjmiemy jako wierzchołek, to posiadać on będzie takie dane jak imię, nazwisko, wiek, wzrost itp. Jeśli potrzebowalibyśmy dokonać jakichś zmian w strukturze wierzchołka wystarczy dopisać interesujące nas instrukcje na początku procedury DFS-ODWIEDZAJ (przed lub po pokolorowaniu na szaro). (11 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com