Przeszukiwanie w głąb (DFS)
Thomashek
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.
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];
FILEplik=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
Spoko, fajne, przydalby sie jedynie przyklad jakis praktyczny (albo w C albo w Pascalu).
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).