1-) VERİYAPILARI - Derin Öncelikli Arama (Depth First Search , DFS)

DFS veri yapısı olarak genellikle STACK yani yığın kullanır.Derin öncelikli arama algoritması olduğu için amacımız mümkün olduğunca derine inmektir.  ÇALIŞMA ZAMANI= O(N+K)

KABA KOD:

ÖRN 1:

1- A dan başla

2- A’nın komşularına bak B, D ve E doğrudan gidilebilecek komşu düğümlerdir.

3- B’ye ilerle. Yığına A’yı ekle  push(A) B düğümündeyken yığına push(B) girer.

4- B düğümünden gidilebilecek komşulara baktığımızda C düğümü olduğu görüyoruz. push(C).

5- C düğümünden E ve F düğümlerine gidilebiliyor. F düğümüne gidelim. push(F)

6- F düğümünden E düğümüne gidelim. push(E).

7- E düğümünden daha önce ziyaret edildiği için C ve A düğümlerine gitmeyip sadece D düğümüne gidelim. push(D)

8- D düğümünden gidilmemiş komşu düğüm kalmadığı için tekrar başlangıç noktamıza dönelim. Böylece tüm düğümleri bir kez ziyaret edecek şekilde gezmiş olduk.

Şimdi stack durumumuza bir göz atalım. Öncelikle her bir komşu ziyaretinde push ile düğümleri yığına dahil ettiğimizi fark etmişsinizdir. Burada LIFO yani Last In First Out bir başka deyişle yığın veri yapısının özelliği olan son giren ilk çıkar mantığı ile push ile eleman aldıkça pop ile elemanları dışarı çıkarmak gerekiyor. Yani F düğümü girdiğinde bir önceki adımdan kalma son giren konumundaki C düğümü yığından çıkar.  Bu şekilde yığın kodlandığında her bir adımda girenler ve çıkanlar olacaktır. Algoritmada başlangıç düğümü farklı seçildiğinde gidilecek yolların sırası değişebilir ancak sonucu değişmeyecektir.

ÖRN 2:

A=gry

B=gry

E=gry

D=gry

C=gry

F=gry

F=black

C=black

D=black

E=black

B=black

A=black

ÖRN 3: