: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > grafy >

P R Z E S Z U K A N I E   G R A F U   W   G Ł Ą B   ( D F S )

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Przeszukanie grafu w głąb (DFS) polega na takim przejściu przez graf, aby każdy wierzchołek został odwiedzony dokładnie jeden raz - odwiedzane są wszystkie wierzchołki grafu, czyli odmiennie niż w przeszukiwaniu wszerz, gdzie odwiedzone zostaną tylko wierzchołki osiągalne z wierzchołka źródłowego. W odróżnieniu od algorytmu BFS przeszukiwanie w głąb jest algorytmem rekurencyjnym, pozwalającym zebrać sporo informacji o strukturze grafu.

Odwiedzenie wierzchołka u grafu polega na:

  • pokolorowaniu wierzchołka u na szaro,

  • odwiedzeniu wszystkich białych następników wierzchołka u,

  • pokolorowaniu wierzchołka u na czarno.

Podobnie jak miało to miejsce w przeszukiwaniu wszerz w tablicy d zapisywane są poprzedniki odwiedzanych wierzchołków: jeśli z wierzchołka u przemieszczamy się do białego następnika v, to w tablicy d w komórce v wpisujemy wartość u (d[v]:=u).

Odpowiednikiem tablicy głębokości g z przeszukiwania wszerz są tutaj dwie tablice g1 i g2. Do tablicy g1 wpisywane są kroki algorytmu, w których wierzchołek został pokolorowany na szaro, do tablicy g2 kroki algorytmu, w których nastąpiło kolorowanie wierzchołka na czarno. Owe kroki algorytmu, to wartość pewnej zmiennej całkowitej, np. czas, która począkowo ma wartość zero, zaś przed każdym kolorowaniem na szaro lub czarno zwiększa swoją wartość o 1.

 

DANE:
  n - liczba wierzchołków grafu
  k - liczba krawędzi grafu
  a - graf skierowany lub nieskierowany - macierz sąsiedztwa
      a[i, j] = True, gdy istnieje krawędź (i, j)
WYNIK:
  tablice "g1" i "g2" kroków odwiedzania wierzchołków grafu
  tablica "d", w której zapisano przebyte ścieżki
    jeżeli d[i]=0, to wierzchołek "i" nie został osiągnięty z żadnego innego wierzchołka
      (nie oznacza to wcale, że nie ma poprzedników)
    jeżeli d[i]>0, liczba d[i] jest numerem poprzednika wierzchołka o numerze "i"
    i-d[i]-d[d[i]]-d[d[d[i]]]-...-j - odwrócona przebyta ścieżka "j"-...-"i"
Const
  MaxIloscWezlow = 1000;

Type
  TypWezla = Word;
  Kolory   = (bialy, szary, czarny);
  Barwy    = Array[1..MaxIloscWezlow] Of Kolory;

  Graf     = Array[1..MaxIloscWezlow, 1..MaxIloscWezlow] Of Boolean;


Var
  a      : Graf;
  b      : Barwy;
  d      : Array[1..MaxIloscWezlow] Of TypWezla;
  g1, g2 : Array[1..MaxIloscWezlow] Of TypWezla;
  n, k   : TypWezla;

Odwiedź wierzchołek k

  1. Do tablicy g1 wpisz krok algorytmu

  2. Pokoloruj wierzchołek k na szaro

  3. Dla każdego białego następnika j wierzchołka k:

    • Wierzchołkowi j przypisz poprzednik k w tablicy ścieżek d

    • Odwiedź wierzchołek j

  4. Do tablicy g2 wpisz krok zakończenia odwiedzania następników

  5. Pokoloruj wierzchołek k na czarno

Procedure Odwiedz(k : TypWezla; Var krok : TypWezla);
Var
  j : TypWezla;
Begin
  krok:=krok+1;
  g1[k]:=krok;
  b[k]:=szary;
  For j:=1 To n Do
    If a[k, j] And (b[j]=bialy) Then
      Begin
        d[j]:=k;
        Odwiedz(j, krok);
      End;
  krok:=krok+1;
  g2[k]:=krok;
  b[k]:=czarny;
End;

Pozostała część przykładowego programu:

Var
  i, j, t, czas : TypWezla;

Begin
  Write('Ilosc wierzcholkow = ');
  ReadLn(n);
  Write('Ilosc krawedzi = ');
  ReadLn(k);

  {Inicjacja tablic}
  For i:=1 To n Do
    For j:=1 To n Do a[i, j]:=False;
  For i:=1 To n Do
    Begin
      d[i]:=0;
      g1[i]:=0;
      g2[i]:=0;
      b[i]:=bialy;
    End;

  {Wczytaj krawedzie}
  For t:=1 To k Do
    Begin
      ReadLn(i, j);
      a[i, j]:=True;
    End;

  {Odwiedz wszystkie biale wierzcholki grafu}
  czas:=0;
  For i:=1 To n Do
    If b[i]=bialy Then Odwiedz(i, czas);


  WriteLn('Wierzcholek : Rozpoczeto : Zakonczono :');
  For i:=1 To n Do
    WriteLn(i, ' : ', g1[i], ' : ', g2[i]);
  ReadLn;
End.
Ilosc wierzcholkow = 7
Ilosc krawedzi = 11
1 2
3 7
4 1
4 5
4 6
5 3
5 4
5 7
6 6
7 1
7 2
Wierzcholek : Rozpoczeto : Zakonczono :
1 : 1 : 4
2 : 2 : 3
3 : 5 : 8
4 : 9 : 14
5 : 10 : 11
6 : 12 : 13
7 : 6 : 7