Przeszukiwanie grafu w głąb (DFS)

01.10.2010 - Michał Karpiński
Trudność

Kolorowanie wierzchołków

Na poprzedniej stronie kilka razy użyte zostały słowa „odwiedzony”, albo „nieodwiedzony” - są to stany w jakich znajduje się dany wierzchołek podczas działania algorytmu. Pytanie, które się teraz nasuwa to:

Jak zapamiętywać moment odwiedzenia wierzchołka tak, żeby omyłkowo nie przejść przez niego drugi raz?

Otóż wymyślono sprytny sposób na rozwiązanie tego problemu – po prostu kolorujemy wierzchołki.

Na początek dobrze jest określić jaki kolor będzie przyjmował wierzchołek w danym momencie działania algorytmu. Wierzchołek może być:

  • BIAŁY, gdy nie został jeszcze odwiedzony

  • SZARY, gdy zostaje odwiedzony po raz pierwszy podczas przeszukiwania

  • CZARNY, gdy zostaje przetworzony, czyli wszyscy jego sąsiedzi zostali już przeszukani

Wierzchołek podczas przeszukiwania zmienia swój kolor kolejno na biały, szary i czarny. Łatwo jest wywnioskować, że na początku wszystkie wierzchołki są pokolorowane na biało, a gdy algorytm zakończy działanie, to wszystkie wierzchołki są czarne.

Aby przybliżyć ideę kolorowania wierzchołków, przeanalizujmy krok po kroku prosty przykład. Załóżmy, że mamy jakiś graf i ustaliliśmy dla niego wierzchołek startowy:

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com