Kuyruk kullanımı

BFS'nin queue ile uygulandığını öğrenirsin.

Kuyruk kullanımı

BFS'nin kalbinde bir kuyruk (queue) vardır. Yeni keşfedilen düğümler kuyruğun sonuna eklenir, işlenecek düğüm baştan alınır.

Bu FIFO düzeni, düğümlerin uzaklık sırasına göre işlenmesini sağlar; küçük uzaklık önce işlenir.

Kuyruk boşaldığında BFS tamamlanmış olur; başka keşfedilecek düğüm kalmaz.

Frontier kavramı

Kuyruğa frontier (cephe) denir: bir sonraki katmana genişlemek için bekleyen düğümleri tutar.

Frontier, keşfedilmiş ama henüz işlenmemiş düğümleri tutar; bu ayrım BFS'nin temelidir.

Frontier boşaldığında tüm ulaşılabilir düğümler işlenmiş demektir; arama biter.

Uygulama Kuyruk boyutu izi

bfs_queue_max(graph, start) yaz. BFS sırasında kuyruğun en büyük boyutunu döndür. print(bfs_queue_max({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)) ile 2 yazdır.

Örnek çözümü göster

def bfs_queue_max(graph, start):
    # Kuyruğun en büyük boyu
    visited = set()
    queue = [start]
    max_size = 1
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            for nb in graph[node]:
                if nb not in visited:
                    queue.append(nb)
            if len(queue) > max_size:
                max_size = len(queue)
    return max_size
print(bfs_queue_max({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))

Kendini test et

Kuyruk işlemi
```
node = queue.____
```
Cevabı göster
```
node = queue.pop(0)
```
Kuyruk kullanımı: kavramları eşleştir

frontier

Bekleyen düğümler
pop(0)

Baştan al
append

Sona ekle
FIFO

Sıra ilkesi
BFS'de yeni keşfedilen düğüm nereye eklenir?
- Kuyruğun sonuna
- Yığına
- Kuyruğun başına
- Heap köküne
Cevabı göster

Kuyruğun sonuna — Kuyruğun sonuna.

Sıradaki ders: Ziyaret işaretleme

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler