DFS mantığı
- Algoritmalar kursu
- Orta seviye
- Ders 57/80
- 4 dk
Bir dalı sonuna kadar takip eden derin öncelikli aramayı öğrenirsin.
DFS mantığı
Derin öncelikli arama (DFS), bir dalı sonuna kadar takip eder, çıkmaza girince geri döner.
Bu yüzden DFS, recursion ya da yığın (stack) ile doğal olarak uygulanır; derine inme önceliklidir.
DFS, döngü tespiti, topolojik sıralama ve yol bulmada sıkça kullanılır; karmaşıklığı O(V + E) olur.
Geri izleme
Çıkmaz sokakta geri dönüp başka bir dala geçmeye backtracking denir. DFS'in temel davranışı budur.
Geri dönen dalların durumu korunur; böylece yol tamamlanır ve hiçbir dal atlanmaz.
Backtracking sayesinde DFS, döngüsel graph'larda bile her düğümü güvenle ziyaret eder.
Uygulama DFS sırası
dfs_order(graph, start) yaz. Yığınla DFS yapıp ziyaret sırasını döndür. print(dfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)) ile [0, 2, 3, 1] yazdır.
Başlangıç kodu
def dfs_order(graph, start):
# Yığınla DFS yapÖrnek çözüm
def dfs_order(graph, start):
# Yığınla DFS yap
visited = []
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.append(node)
for nb in reversed(graph[node]):
if nb not in visited:
stack.append(nb)
return visited
print(dfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))Beklenen çıktı
[0, 2, 3, 1]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 DFS hangi veri yapısıyla doğal uygulanır?
- Yığın veya recursion Doğru cevap
- Sadece kuyruk
- Sadece heap
- Hash tablosu
Açıklama: Yığın veya recursion.
2 DFS başlangıcı
stack = [____]stack = [start]Açıklama: start doğru.
3 DFS mantığı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
DFS |
Derin |
stack |
LIFO |
BFS |
Katman |
recursion |
Kendini çağırır |