Kuyruk kullanımı
- Algoritmalar kursu
- Orta seviye
- Ders 54/80
- 4 dk
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.
Başlangıç kodu
def bfs_queue_max(graph, start):
# Kuyruğun en büyük boyuÖrnek çözüm
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))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kuyruk işlemi
node = queue.____node = queue.pop(0)Açıklama: pop(0) doğru.
2 Kuyruk kullanımı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
frontier |
Bekleyen düğümler |
pop(0) |
Baştan al |
append |
Sona ekle |
FIFO |
Sıra ilkesi |
3 BFS'de yeni keşfedilen düğüm nereye eklenir?
- Kuyruğun sonuna Doğru cevap
- Yığına
- Kuyruğun başına
- Heap köküne
Açıklama: Kuyruğun sonuna.