BFS mantığı
- Algoritmalar kursu
- Orta seviye
- Ders 53/80
- 4 dk
Başlangıç düğümünden dışa doğru kat kat dolaşan algoritmayı öğrenirsin.
BFS katmanları
Geniş öncelikli arama (BFS), başlangıç düğümünden başlayıp dışa doğru kat kat ilerler.
Her katmanda bir adım uzaklıktaki tüm düğümler işlenir. Bu sayede BFS, yönsüz graph'ta en az kenarlı yolu verir.
BFS, kısa yol ve ulaşılabilirlik sorunlarında sıkça kullanılır; kuyruk ile uygulanır.
Sıra önceliği
BFS, bir düğümü işlerken komşularını sıraya ekler. İlk giren ilk çıkar (FIFO) ilkesi geçerlidir.
Bu sayede uzaklığı küçük olan düğümler her zaman önce işlenir; sıra bozulmaz.
Kuyruğa ekleme sondan, çıkarma baştan yapılır; böylece katman sırası korunur.
Uygulama Katmanları yazdır
bfs_order(graph, start) yaz. BFS ile düğümleri ziyaret sırasına göre listele ve döndür. print(bfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)) ile [0, 1, 2, 3] yazdır.
Başlangıç kodu
def bfs_order(graph, start):
# BFS ile ziyaret sırasını döndürÖrnek çözüm
def bfs_order(graph, start):
# BFS ile ziyaret sırasını döndür
visited = []
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
for nb in graph[node]:
if nb not in visited:
queue.append(nb)
return visited
print(bfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))Beklenen çıktı
[0, 1, 2, 3]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 BFS hangi veri yapısını kullanır?
- Yığın
- Kuyruk Doğru cevap
- Yığın ve kuyruk
- Heap
Açıklama: Kuyruk.
2 BFS başlangıcı
queue = [____]queue = [start]Açıklama: start doğru.
3 BFS mantığı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
BFS |
Katman |
kuyruk |
FIFO |
DFS |
Derin |
heap |
Öncelik |