Przeszukiwanie w głąb, inaczej zwane DFS (ang. Depth-First Search), jest algorytmem służącym do przeglądania kolejnych wierzchołków grafu. Polega na przetwarzaniu krawędzi każdego, ostatnio odwiedzonego wierzchołka, który nie został wcześniej wywołany, dopóty, dopóki istnieją krawędzie prowadzące z tego wierzchołka. Po przeanalizowaniu wszystkich krawędzi prowadzących z danego wierzchołka, algorytm cofa się i przetwarza dalej, dotąd nie analizowane, krawędzie wierzchołka, z którego został wywołany. Operację należy wykonać na każdym, dotąd nie analizowanym wierzchołku (przy niektórych zastosowaniach jest to zbędne).
Przy niektórych zastosowaniach niezbędne jest zapamiętanie czasu odwiedzenia i czasu przetworzenia każdego wierzchołka (najczęściej każda operacja rozpoczęcia przetwarzania i końca przetworzenia zajmuje umownie jedną jednostkę czasu).
Rys. 1. Działanie algorytmu przeszukiwania w głąb na przykładowym grafie
Czas działania algorytmu wynosi O(V+E), gdzie V to ilość wierzchołków oraz E to ilość krawędzi w analizowanym grafie.
Zastosowanie
Przeszukiwanie w głąb jest jednym z podstawowych algorytmów grafowych. Posiada szerokie zastosowanie. Jego zmodyfikowana wersja służy jako algorytm do znajdowania najkrótszej ścieżki pomiędzy źródłem a każdym wierzchołkiem (choć pesymistyczny czas działania nie jest zadawalający). Często jest używany do sprawdzenia, czy istnieje droga między wybranym wierzchołkiem (źródłem) a pozostałymi. Z przeszukiwania w głąb korzysta wiele innych algorytmów, w tym m. in.:
Implementacja
Poniżej podana przykładowa implementacja algorytmu (pseudokod), łącznie z przypisywaniem czasów odwiedzenia i przetworzenia każdego wierzchołka, co jest przydatne z kolei przy implementacji niektórych innych algorytmów wymienionych wyżej.
Główna procedura wygląda następująco:
<font name="Courier New">DFS ( wierzchołek )
{
czas = czas + 1
czas_odwiedzenia[wierzchołek] = czas
for każda krawędź wychodząca z wierzchołek do
{
if czas_odwiedzenia[wierzchołek, do którego prowadzi ta krawędź] == 0 then
{
wywołaj procedurę DFS( wierzchołek, do którego prowadzi ta krawędź )
}
}
czas = czas + 1
czas_przetworzenia[wierzchołek] = czas
}</span>
Warunek wewnątrz pętli dokonuje sprawdzenia, czy wierzchołek, do którego prowadzi krawędź, nie został już odwiedzony, gdyż zgodnie z opisem algorytmu, procedurę należy wywołać tylko jeden raz dla każdego wierzchołka. Powyższą procedurę należy wywołać dla każdego wierzchołka grafu, którego czas_odwiedzenia jest równy 0 (w przypadku, gdy graf nie jest spójny).
Jeśli nie jest wymagane zapamiętanie czasu odwiedzenia i przetworzenia każdego wierzchołka, należy pominąć przy implementacji dwie pierwsze i dwie ostatnie linie pseudokodu wewnątrz procedury DFS.
Przy sprawdzaniu, czy istnieje droga z danego wierzchołka do pozostałych, należy wywołać procedurę DFS tylko dla wierzchołka źródłowego, a wewnątrz pętli zamieścić warunek przerywający operację przeszukania, gdy zostanie odwiedzony wierzchołek docelowy. Jeśli nie nastąpi przerwanie przeszukiwania, oznacza to, iż droga pomiędzy tymi wierzchołkami nie istnieje.
Później dodam jeszcze ładny obrazek do tego artykułu.
EDIT: Dodałem.
PS. Niech ktoś skasuje Image:dfs.jpg (za duży był, zmieniłem na gifa).
Spoko, fajne, przydalby sie jedynie przyklad jakis praktyczny (albo w C albo w Pascalu).
Ma ktoś to napisane w Pascalu??
/
Program który wyświetla koszt Minimalnego Drzewa Rozpinającego
dane wczytywane z pliku tekstowego
/
#include<algorithm>
#include <fstream>
#include <conio.h>
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int tab[7000], ile[7000]; // 7000 - to liczba wszystkich elementów
int fa;
int Find(int a) { return (tab[a]==a) ? a : (tab[a] = fa); }
const int MAX = 10;
char wiersz[MAX];
FILE*plik=fopen("c:\lista.txt","r");
bool Union(int a, int b)
{
int fa = Find(a); // szukaj reprezentanta zbioru zawierającego element 'a'
int fb = Find(b); // szukaj reprezentanta zbioru zawierającego element 'b'
}
pair< int,pair<int,int> > Edges[300000]; // tablica krawędzi do posortowania
int main(void)
{
//ifstream plik_odczyt("c:/lista.txt");
fopen("c:\lista.txt","r");
for (int i=0; i<m; i++)
{
plik_odczyt << ("%d %d %d", &a, &b, &c); a--; b--;; wierzchołki i ich waga
fscanf(plik, "%d %d %d", &a, &b, &c);a--; b--;
Edges[i] = make_pair( c, make_pair(a,b) );
}
sort(Edges, Edges+m);
for (int i=0; i<m; i++)
if ( Union(Edges[i].second.first,Edges[i].second.second) )
{
cost += Edges[i].first;
// krawędz drzewa : Edges[i].second.first -- Edges[i].second.second
}
fclose(plik);
}
Bardziej obcykani poprawią sobie te błędy