Graf geçişi için iki temel algoritma: Genişlik Öncelikli Arama (BFS) ve Derinlik Öncelikli Arama (DFS).
Genişlik Öncelikli Arama (BFS)
Başlangıç düğümünden başlayarak katman katman, tüm komşuları ziyaret eden algoritma.
Çalışma Prensibi:
- Başlangıç düğümünü kuyruğa ekle
- Kuyruk boş olmadığı sürece:
- Kuyruğun önündeki düğümü çıkar
- Ziyaret edilmemiş komşularını kuyruğa ekle
Kullanım Alanları:
- En kısa yol bulma (ağırlıksız graflarda)
- Sosyal ağlarda bağlantı seviyesi
- Web crawling
Derinlik Öncelikli Arama (DFS)
Mümkün olduğunca derinlemesine giden, sonra geri dönen algoritma.
Çalışma Prensibi:
- Başlangıç düğümünü ziyaret et
- Ziyaret edilmemiş komşuları için DFS çağır
- Geri dön (backtrack)
Kullanım Alanları:
- Döngü tespiti
- Topolojik sıralama
- Labirent çözme
- Bağlı bileşen bulma
BFS vs DFS Karşılaştırması
| Özellik | BFS | DFS |
|---|---|---|
| Veri Yapısı | Kuyruk | Yığın/Özyineleme |
| En Kısa Yol | Bulur | Bulmaz |
| Bellek | Daha fazla | Daha az |