Time and Space Complexity
Coddy'nin Breadth-First Search - Graf Algoritmaları kursunda ders 7 / 9.
Zaman Karmaşıklığı:
- O(V + E)
- Her düğüm bir kez kuyruğa eklenir ve kuyruktan çıkarılır ve her kenar sabit sayıda incelenir.
Alan Karmaşıklığı:
- O(V + E)
- Komşuluk listesi her kenarı saklar ve kuyruk ile ziyaret edilenler dizisi V düğüme kadar veri tutar.
Özet:
- BFS, bir kuyruk kullanarak katmanlar halinde keşif yapar ve uzaktaki düğümlerden önce yakındaki düğümleri ziyaret eder.
- Bu katmanlı düzen, onu ağırlıksız grafiklerdeki en kısa yollar için başvurulacak algoritma haline getirir.
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.
Breadth-First Search - 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