Time and Space Complexity
Coddy'nin Derinlik Öncelikli Arama - Graf Algoritmaları kursunda ders 7 / 9.
Zaman Karmaşıklığı:
- O(V + E)
- Komşuluk listesini oluşturmak her kenara bir kez dokunur ve gezinme işlemi her düğümü ziyaret ederek her kenara sabit sayıda bakar.
Alan Karmaşıklığı:
- O(V + E)
- Komşuluk listesi her kenarı saklar; ziyaret edilenler dizisi (visited array) ve yığın (stack) ise V düğüme kadar veri tutar.
Özet:
- DFS önce derinlemesine keşfeder, ziyaret edilmemiş komşu kalmadığında geri izleme (backtracking) yapar.
- Doğrusal zamanda çalışır ve birçok graf algoritmasının temelini oluşturur.
Kendin dene
Bu ders bir kod alıştırması içermiyor.
Kendini test etBu ders kısa bir quiz içerir. Soruları yanıtlamak ve ilerlemeni kaydetmek için derse başla.
Derinlik Öncelikli Arama - Graf Algoritmaları bölümündeki tüm dersler
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity