Przeszukiwanie grafu w głąb (DFS)

01.10.2010 - Michał Karpiński
Trudność

Dodatkowy atrybut - czas

Wiemy już bardzo dobrze jak przeszukiwać graf metodą „w głąb”. Kolorowanie zapewne zrobiło się trochę nudne. Pora rozszerzyć procedurę DFS z poprzedniej strony. W tym rozdziale zajmiemy się informacją, która przydaje się przy wielu algorytmach wykorzystujących przeszukiwanie w głąb – czasem.

Tak na prawdę to chcemy wiedzieć, w którym momencie nastąpiło odwiedzenie wierzchołka i kiedy został on przetworzony. Podobnie jak przy określeniu koloru, zdefiniujemy teraz kilka nowych zmiennych:

  • d[u] – jest to czas, w którym odwiedziliśmy wierzchołek u (pokolorowaliśmy go na szaro)

  • f[u] – czas, w którym u zostało przetworzone (pokolorowane na czarno)

  • time – zmienna globalna. Zegar, który odmierza czas

Dokonujemy lekkiej modyfikacji w pseudokodzie:

Zmiana dokonana w procedurze DFS jest raczej oczywista – zanim zaczniemy przeszukiwanie najpierw trzeba wyzerować licznik czasu. W procedurze DFS-ODWIEDZAJ zwiększamy zmienną globalną time o 1 zawsze gdy odwiedzamy nowy wierzchołek oraz gdy kończymy przeglądać jego sąsiadów. Innymi słowy – czas zwiększa się zawsze gdy któryś z wierzchołków zmienia kolor. W odpowiednich miejscach aktualizujemy też atrybuty d oraz f dla danego wierzchołka.

Zobaczmy jak to działa w praktyce:

W każdym wierzchołku liczba po lewej stronie oznacza czas odwiedzenia, a po prawej stronie - czas przetworzenia.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com