Przeszukiwanie grafu w głąb (DFS)

01.10.2010 - Michał Karpiński
Trudność

Pseudokod - pierwsza przymiarka

Nadszedł 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:

  • color[v] – atrybut określający aktualny kolor wierzchołka v. Wiemy już, że kolor może przyjmować trzy wartości: BIAŁY, SZARY i CZARNY

  • sasiad[u] – jest to lista sąsiadów wierzchołka u, czyli lista wierzchołków bezpośrednio połączonych z u, do których można dojść z u.

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:

  • najpierw kolorujemy wszystkie wierzchołki grafu na biało

  • w następnej pętli badamy wszystkie wierzchołki grafu G i gdy trafimy na biały wierzchołek (czyli taki, który nie został jeszcze odwiedzony) uruchamiamy procedurę DFS-ODWIEDZAJ na tym wierzchołku. Staje się on wierzchołkiem startowym, z którego rozpoczynamy przeszukiwanie

  • DFS-ODWIEDZAJ to procedura, która „odwiedza” dany wierzchołek (jak sama nazwa wskazuje). Proces ten składa się z trzech części. Najpierw kolorujemy podany wierzchołek na szaro. Następnie przeglądamy wszystkich jego sąsiadów i odwiedzamy pierwszy biały wierzchołek na jaki natrafimy. Po wyjściu z pętli wszyscy sąsiedzi są już przetworzeni, czyli wystarczy teraz pokolorować nasz wierzchołek na czarno i zakończyć procedurę.

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).

4.272725
Twoja ocena: Brak Ocena: 4.3 (11 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com