Ziyaret işaretleme

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.

Örnek çözümü göster

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

Kendini test et

Ziyaret işaretleme: kavramları eşleştir

visited

Tekrarı önler
küme

Hızlı arama
graph

Komşular
queue

Sıra
Visited kümesinin görevi nedir?
- Hız artırmak
- Tekrarı önlemek
- Ağırlık saklamak
- Sırayı korumak
Cevabı göster

Tekrarı önlemek — Tekrarı önlemek.

Ziyaret ekleme

if node not in visited:
    visited.____(node)

Cevabı göster

if node not in visited:
    visited.add(node)

Sıradaki ders: Özet - BFS

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler