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.