Özet - DFS
- Algoritmalar kursu
- Orta seviye
- Ders 60/80
- 4 dk
Bir graph'ta DFS uygulayıp sırayı yazdıran mini görev yaparsın.
Özet - DFS
DFS; yığın veya recursion ile derine inen, çıkmazda geri izleme yapan aramadır. Yol bulma, döngü tespiti ve topolojik sıralamada kullanılır.
Bu mini görevde DFS uygulayıp ziyaret sırasını yazdıracaksın; tüm adımları birleştir.
DFS, derin graph'ları verimli gezer; bu yüzden bağlantı analizi ve sıralama için tercih edilir.
Uygulama DFS yazdır
dfs_print(graph, start) yaz. Yığınla DFS yapıp ziyaret sırasını print() ile yazdır. Çıktı: [0, 2, 3, 1].
Başlangıç kodu
def dfs_print(graph, start):
# DFS sırasını yazdırÖrnek çözüm
def dfs_print(graph, start):
# DFS sırasını yazdır
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)
print(visited)
dfs_print({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 Özet - DFS: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
DFS |
Yığın |
recursion |
Kendini çağırır |
backtrack |
Geri dön |
visited |
Tekrar yok |
2 Yığın işlemi
Soru
node = stack.____
Cevap
node = stack.pop()Açıklama: pop() doğru.
3 DFS'nin zaman karmaşıklığı nedir?
- O(V log V)
- O(V + E) Doğru cevap
- O(E^2)
- O(V!)
Açıklama: O(V + E).