subota, 22. prosinca 2012.

Pripreme za algoritme(13)

DFS


Kod obilaska grafa u dubinu krećemo od početnog čvora, pronalazimo prvi povezan s njim (koji nismo već prije posjetili) i to nam postaje početni čvor za dalji obilazak. Kad obiđemo jednu granu vraćamo se roditeljskom čvoru i ulazimo u novu granu. Obilazak je rekurzivan (ponavlja se isti postupak na nižem nivou) pa je opravdano koristiti rekurzivnu proceduru.


  1. unos podataka o čvorovima i vezama
  2. kreiramo matricu susjedstva
  3. za sve postojeće čvorove od 1 do N:
    • ako trenutni čvor nije posjećen pozivamo funkciju obilazak(trenutni)
Funkcija obilazak(čvor) je rekurzivna funkcija (unutar bloka naredbi opet poziva funkciju obilazak):
  1. označi čvor za koji smo pozvali funkciju kao posjećen (u nizu bio, element bio[čvor] postaje true ili 1
  2. za sve postojeće čvorove od 1 do N provjerava
    • ako postoji veza prema čvoru i ako to nije trenutni čvor za koji smo pozvali funkciju i ako čvor nije prije posjećen (veza[trenutni,j]=1, j<>trenutni, bio[j]=false)
      • poziva funkciju posjet(j);
Redoslijed kojim su čvorovi prijeđeni možemo zapisati u nekom vanjskom polju.

U slučaju prikazanom na slici redoslijed obilaska će biti:
1 ide u 2 vraća se u 1
1 ide u 3 ide u 5 ide u 4 vraća se u 5 vraća se u 3
3 ide u 6 ide u 7 ide u 8 vraća se u 7 vraća se u 6 vraća se u 3

U sljedećoj lekciji ćemo ovu ideju prikazati u kodu.

Nema komentara:

Objavi komentar