BFS mantığı

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.

Örnek çözümü göster

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))

Kendini test et

BFS hangi veri yapısını kullanır?
- Yığın
- Kuyruk
- Yığın ve kuyruk
- Heap
Cevabı göster

Kuyruk — Kuyruk.
BFS başlangıcı
```
queue = [____]
```
Cevabı göster
```
queue = [start]
```
BFS mantığı: kavramları eşleştir

BFS

Katman
kuyruk

FIFO
DFS

Derin
heap

Öncelik

Sıradaki ders: Kuyruk kullanımı

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler