Przeszukiwanie grafu w głąb (DFS)

01.10.2010 - Michał Karpiński
Trudność

Algorytm przeszukiwania w głąb ( ang. depth first search ) jest jedną z najprostszych metod przechodzenia po grafie. Jednocześnie, metoda ta jest używana jako podstawa do wielu bardziej skomplikowanych algorytmów grafowych. Z tego powodu wiedza na temat przechodzenia grafu w głąb jest niezbędna dla osób rozpoczynających swoją przygodę z algorytmiką.

Idea jest bardzo prosta – sięgamy w grafie „głębiej” o ile jest to możliwe. Najpierw wybieramy wierzchołek, z którego rozpoczniemy przeszukiwanie (nazwijmy go wierzchołkiem startowym). Następnie przechodzimy z wybranego wierzchołka do któregokolwiek z jego sąsiadów, który nie został jeszcze odwiedzony.

Podstawowe informacje na temat Teorii Grafów można znaleźć w tym artykule

Powtarzamy powyższy krok do momentu, gdy wszyscy sąsiedzi wierzchołka v, w którym się aktualnie znajdujemy, zostali już odwiedzeni. Cofamy się wtedy do wierzchołka, z którego doszliśmy do v i szukamy innego nieodwiedzonego jeszcze wierzchołka. Proces ten jest kontynuowany do momentu, kiedy odwiedziliśmy wszystkie wierzchołki osiągalne z wierzchołka startowego.

Po wykonaniu jednego takiego przejścia, jeśli w grafie pozostały jeszcze jakieś wierzchołki nieodwiedzone, to znów wybieramy wierzchołek startowy i przeszukujemy dalej. W przeciwnym wypadku kończymy działanie algorytmu, gdyż wszystkie wierzchołki zostały już odwiedzone.

Oczywistym jest, że sam opis działania przeszukiwania w głąb nie wystarczy, aby w pełni zrozumieć „o co tak właściwie chodzi”. Z pomocą przychodzi nam prosta animacja pokazująca przykładowe przejście po grafie.

Zabawa nie kończy się tylko na kolorowej animacji. W dalszej części tego artykułu poznamy „dogłębniej” ten prosty algorytm przeszukiwania. Omówimy własności oraz zapiszemy go w postaci pseudo-kodu. Następnie omówimy kilka łatwych problemów algorytmicznych, które wykorzystują technikę przeszukiwania w głąb.

ZAPRASZAM DO LEKTURY

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com