DFS Algoritması graflar üzerinde kullanılan bir arama algoritmasıdır. Tıpkı BFS algoritması gibi tüm düğümleri gezmeyi hedefler. Açılımı Depth First Search şeklindedir.
 |
| dfs algoritması |
DFS Algoritması
Temel mantığı şu şekildedir, "Gidebildiğin yerin sonuna kadar git, sonra geri dön, bulduğun noktadan aynı mantıkla ilerle"
Tabii bu açıklama çok genel oldu. Mesela BFS Algoritmasında önce komşular ziyaret edilir daha sonra komşuların komşularına gidilirdi. Yani aynı seviyedeki düğümler öncelikli olarak ziyaret edilmeliydi. Ancak DFS'de durum tam tersi, gidilebildiği noktaya kadar gidilir, sonra geri dönülür, gidilmeyen noktalara gidilir.
Algoritma Uzmanı diğerleri gibi goygoy yapmaz, sizlere adım adım her şeyi gösterir :) Haydi o zaman teoriyi bırakalım, algoritma nasıl uygulanır bir bakalım.
Adım Adım DFS Algoritması Uygulaması
 |
| graf yapımız |
1. Adım:
Bağlangıç düğümü seçilir, Yığına eklenir push(A)
Yığına Eklenen Visited Olarak İşaretlenir
Ziyaret Edilenler: [A]
Yığın Durumu [A]
2. Adım
A'nın İlk Komşusu bulunur ve Yığına Eklenilir push(B) (not: S de olabilirdi, fark etmez)
Yığına Eklenen Visited Olarak İşaretlenir
Ziyaret Edilenler: [A, B] -B Eklendi
Yığın Durumu [A, B] -B Eklendi
3. Adım
bir önceki adımda B düğümüne geldiğimiz için B'nin ziyaret edilmemiş komşusu aranır
B'nin komşusu olmadığından yığından çıkarılır. pop()
Ziyaret Edilenler [A, B] -aynı kaldı
Yığın Durumu [A] - B Çıkartıldı
4. Adım
Yığında kalan eleman A olduğundan A'nın ziyaret edilmemiş komşusu aranır ve bulunur (S)
S yığına eklenilir, push(S), S visited olarak işaretlenir
Ziyaret Edilenler [A, B, S]
Yığın Durumu [A, S] - S Eklendi
5. Adım
S düğümünün ziyaret edilmemiş komşusu bulunur ve Yığına eklenir. push(C)
C visited olarak işaretlenir.
Ziyaret Edilenler [A, B, S, C] -C eklendi
Yığın Durumu [A, S, C] -C eklendi
6. Adım
C düğümünün ziyaret edilmemiş komşusu bulunur ve yığına eklenir push(D)
D düğümü visited olarak işaretlenir
Ziyaret Edilenler [A, B, S, C, D] -D eklendi
Yığın Durumu [A, S, C, D] -D eklendi
7. Adım
D düğümünün komşusu yoktur.
D'nin komşusu olmadığı için Stack'ten çıkartılır. pop()
Ziyaret Edilenler [A, B, S, C, D] -aynı kaldı
Yığın Durumu [A, S, C] - D çıkartıldı
8. Adım
C düğümünün ziyaret edilmemiş komşusu aranır ve yığına eklenir. push(E)
E visited olarak işaretlenir
Ziyaret Edilenler [A, B, S, C, D, E] -E eklendi
Yığın Durumu [A, S, C, E] -E eklendi
9. Adım
E düğümünün ziyaret edilmemiş komşusu aranır ve yığına eklenir. push(H)
H visited olarak işaretlenir
Ziyaret Edilenler [A, B, S, C, D, E, H] -H eklendi
Yığın Durumu [A, S, C, E, H] -H eklendi
10.adım
H düğümünün ziyaret edilmemiş komşusu aranır ve yığına eklenir. push(G)
G visited olarak işaretlenir
Ziyaret Edilenler [A, B, S, C, D, E, H, G] -G eklendi
Yığın Durumu [A, S, C, E, H, G] -G eklendi
11.adım
G düğümünün ziyaret edilmemiş komşusu aranır ve yığına eklenir. push(F)
F visited olarak işaretlenir
Ziyaret Edilenler [A, B, S, C, D, E, H, G, F] -F eklendi
Yığın Durumu [A, S, C, E, H, G, F] -F eklendi
dikkat ederseniz tüm düğümleri ekledik, aslında program bundan sonra devam eder, diğer adımlarda her komşu bulamadığında pop işlemi yapar ve yığında eleman kalmayıncaya kadar bu adımları devam ettirir. Program yığın boşalıncaya kadar devam eder.
DFS Algoritması Çalışma Mantığı
1- Bir düğüm seç ve yığına ekle
2- yığının top elemanını visited olarak işaretle
3- yığının top düğümünün !visited olan komşusunu bul ve 2 adımdan devam et. Komşu yoksa dördüncü adıma geç
4- yığından eleman çıkar ve 2. adımdan devam et
Mutlaka Okuyun
Etiketler: bfs algoritması, depth first search, dfs algoritması, dfs algoritması adım adım, dfs algoritması çalışma mantığı
