Ziyaret işaretleme
- Algoritmalar kursu
- Orta seviye
- Ders 55/80
- 4 dk
Ziyaret edilen düğümü işaretleyerek tekrarı önlemeyi öğrenirsin.
Ziyaret işaretleme
Aynı düğümün tekrar işlenmesini önlemek için visited kümesi tutulur. Düğüm ilk görüldüğünde eklenir.
Bu, BFS'nin O(V + E) zamanında bitmesini sağlar; her düğüm ve kenar bir kez işlenir.
visited kümesi olmadan aynı düğüm kuyruğa defalarca girebilir; bu sonsuz döngüye yol açar.
İşaretleme zamanı
Düğüm kuyruğa eklenirken işaretlemek, aynı düğümün kuyruğa iki kez girmesini engeller; bu daha verimlidir.
İşleme sırasında işaretlemek de doğrudur ama kuyruk daha çok yer kaplar; tercih meselesidir.
Erken işaretleme, bellek kullanımını azaltır ve pratikte tercih edilen yöntemdir.
Uygulama Ziyaret sayısı
bfs_count(graph, start) yaz. BFS ile kaç düğümün ziyaret edildiğini döndür. print(bfs_count({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)) ile 4 yazdır.
Başlangıç kodu
def bfs_count(graph, start):
# Ziyaret edilen düğüm sayısıÖrnek çözüm
def bfs_count(graph, start):
# Ziyaret edilen düğüm sayısı
visited = set()
queue = [start]
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)
return len(visited)
print(bfs_count({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))Beklenen çıktı
4
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Ziyaret işaretleme: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
visited |
Tekrarı önler |
küme |
Hızlı arama |
graph |
Komşular |
queue |
Sıra |
2 Visited kümesinin görevi nedir?
- Hız artırmak
- Tekrarı önlemek Doğru cevap
- Ağırlık saklamak
- Sırayı korumak
Açıklama: Tekrarı önlemek.
3 Ziyaret ekleme
if node not in visited:
visited.____(node)if node not in visited:
visited.add(node)Açıklama: add doğru.