Enine Arama

Ağaçlarda seviye sıralı gezinme, düğümleri katman katman ziyaret ediyordu ve bunu bir kuyrukla yapıyordu. Aynı fikir çizgelerde de çalışır — bir farkla: çizgede döngüler vardır ve aynı düğüme birden çok yoldan ulaşılabilir.

Enine arama (breadth-first search), başlangıç düğümünden uzaklığa göre katman katman ilerleyen gezinmedir.

Ziyaret İşaretlemesi

Ağaçta her düğüme tek bir yoldan ulaşılırdı; çizgede bu güvence yoktur. İşaretleme yapılmazsa aynı düğüm defalarca kuyruğa girer ve döngü varsa gezinme hiç bitmez.

Bu nedenle çizge gezinmelerinin tamamı bir ziyaret kümesi tutar. Bir düğüm kuyruğa konurken işaretlenir; işaretli düğüm bir daha eklenmez.

Ziyaret kümesi, çizge gezinmelerini ağaç gezinmelerinden ayıran tek yapısal eklentidir; gerisi aynıdır. İşaretlemenin kuyruğa eklerken yapılması önemlidir. Kuyruktan çıkarırken yapılırsa, aynı düğüm çıkarılmadan önce birden çok kez eklenebilir ve kuyruk gereksiz yere büyür.

Algoritma

from collections import deque

def enine_ara(komsuluk: dict[str, list[str]], baslangic: str):
    """Katman katman gezer; (ziyaret sırası, uzaklıklar, ebeveynler) döndürür."""
    ziyaret = {baslangic}
    uzaklik = {baslangic: 0}
    ebeveyn: dict[str, str | None] = {baslangic: None}
    sira: list[str] = []
    kuyruk = deque([baslangic])

    while kuyruk:
        dugum = kuyruk.popleft()               # ilk giren ilk çıkar
        sira.append(dugum)
        for komsu in komsuluk.get(dugum, []):
            if komsu not in ziyaret:
                ziyaret.add(komsu)             # eklerken işaretle
                uzaklik[komsu] = uzaklik[dugum] + 1
                ebeveyn[komsu] = dugum
                kuyruk.append(komsu)
    return sira, uzaklik, ebeveyn


komsuluk = {
    "bati":   ["kuzey", "guney"],
    "kuzey":  ["bati", "merkez"],
    "guney":  ["bati", "merkez"],
    "merkez": ["kuzey", "guney", "dogu"],
    "dogu":   ["merkez"],
}

sira, uzaklik, ebeveyn = enine_ara(komsuluk, "bati")
print(sira)          # ['bati', 'kuzey', 'guney', 'merkez', 'dogu']
print(uzaklik)       # {'bati': 0, 'kuzey': 1, 'guney': 1, 'merkez': 2, 'dogu': 3}

Ziyaret sırası katmanları izler: önce başlangıç, sonra bir kenar uzaktakiler, sonra iki kenar uzaktakiler. merkez düğümüne hem kuzey hem guney üzerinden ulaşılabilir; işaretleme sayesinde yalnızca ilki dikkate alınır.

Ağırlıksız En Kısa Yol

Enine aramanın en önemli özelliği burada ortaya çıkar: bulduğu uzaklıklar, ağırlıksız çizgede en kısa yol uzunluklarıdır.

Gerekçe katmanlı ilerlemededir. Bir düğüme ilk kez ulaşıldığında, o ana kadar işlenen tüm düğümler daha yakın veya eşit uzaklıktadır; dolayısıyla daha kısa bir yol bulunması olanaksızdır. Bu, kuyruğun ilk giren ilk çıkar davranışının doğrudan sonucudur — yığıt kullanılsaydı güvence ortadan kalkardı.

Ebeveyn kaydı tutulduğunda, yolun kendisi de geri kurulabilir:

def yolu_kur(ebeveyn: dict[str, str | None], hedef: str) -> list[str]:
    """Ebeveyn kayıtlarından hedefe giden yolu geri kurar."""
    if hedef not in ebeveyn:
        return []                              # ulaşılamıyor
    yol = []
    dugum: str | None = hedef
    while dugum is not None:
        yol.append(dugum)
        dugum = ebeveyn[dugum]
    return list(reversed(yol))


print(yolu_kur(ebeveyn, "dogu"))     # ['bati', 'kuzey', 'merkez', 'dogu']
print(yolu_kur(ebeveyn, "yok"))      # []

Yol, hedeften başlayarak geriye izlenir ve ters çevrilir. Aynı teknik, sonraki kursta ele alınacak ağırlıklı en kısa yol algoritmalarında da kullanılır.

Ağırlıklar devreye girdiğinde enine arama yetmez: az sayıda ağır kenar, çok sayıda hafif kenardan pahalı olabilir. O durumda kuyruk yerine öncelik kuyruğu kullanan algoritmalar gerekir; ağaçlar konusundaki yığın bu nedenle çizge algoritmalarının temel yapı taşlarındandır.

Aynı teknik, hedefin de bilindiği aramalarda çift yönlü olarak uygulanabilir: iki arama başlatılır — biri başlangıçtan, biri hedeften — ve ikisi karşılaştığında yol bulunmuş olur. Her arama yarı derinliğe kadar ilerlediği için ziyaret edilen düğüm sayısı belirgin biçimde azalır; dallanma çarpanının yüksek olduğu çizgelerde kazanç büyüktür.

Maliyet

Her düğüm en fazla bir kez kuyruğa girer ve her kenar en fazla iki kez incelenir (yönsüz çizgede her iki uçtan bir kez). Komşuluk listesiyle toplam maliyet:

$$O(\lvert V \rvert + \lvert E \rvert)$$

Bellek maliyeti, kuyrukta aynı anda bulunabilecek en fazla düğüm sayısıdır — yani en geniş katmanın genişliği. Geniş ve sığ çizgelerde bu sayı büyük olabilir; ağaçlardaki seviye sıralı gezinme için yapılan gözlemin aynısıdır.

Çok Kaynaklı Arama

Enine arama tek bir başlangıç düğümüyle sınırlı değildir. Kuyruğa baştan birden çok düğüm konursa, gezinme tüm kaynaklardan aynı anda yayılır ve bulunan uzaklık, en yakın kaynağa olan uzaklıktır.

def cok_kaynakli(komsuluk: dict[str, list[str]], kaynaklar: list[str]) -> dict[str, int]:
    """Her düğüm için en yakın kaynağa uzaklığı döndürür."""
    uzaklik = {k: 0 for k in kaynaklar}
    kuyruk = deque(kaynaklar)
    while kuyruk:
        dugum = kuyruk.popleft()
        for komsu in komsuluk.get(dugum, []):
            if komsu not in uzaklik:
                uzaklik[komsu] = uzaklik[dugum] + 1
                kuyruk.append(komsu)
    return uzaklik


print(cok_kaynakli(komsuluk, ["bati", "dogu"]))
# {'bati': 0, 'dogu': 0, 'kuzey': 1, 'guney': 1, 'merkez': 1}

Tek kaynaklı aramada merkez düğümünün uzaklığı iki idi; iki kaynakla bir olur, çünkü dogu düğümüne komşudur.

Bu kalıp, “her hücrenin en yakın su kaynağına uzaklığı” veya “her düğümün en yakın sunucuya gecikmesi” gibi problemleri, her kaynak için ayrı arama yapmadan tek geçişte çözer. Aynı işi kaynak sayısı kadar arama ile yapmak, maliyeti kaynak sayısıyla çarpardı.

Kullanım Alanları

En az adımlı çözüm. Bir bulmacanın durumları düğüm, hamleler kenar sayıldığında, enine arama en az hamleli çözümü bulur.

Bağlı bileşenler. Her ziyaret edilmemiş düğümden bir arama başlatmak, çizgeyi bileşenlerine ayırır. Ayrık kümeler dersindeki soru burada gezinmeyle yanıtlanır; fark, oradaki yapının kenarlar akış hâlinde gelirken çalışmasıdır.

İki parçalılık sınaması. Katmanlar dönüşümlü olarak iki renge boyanır; aynı katmandaki iki düğüm arasında kenar bulunursa çizge iki parçalı değildir.

Yayılma modelleri. Bir ağda bilginin, bir toplulukta bir etkinin veya bir sistemde bir arızanın kaç adımda nereye ulaştığı.

Ağ tarama. Bağlantılar üzerinden ilerleyen tarayıcılar, başlangıç adresinden uzaklığa göre gezinmek için enine arama kullanır.

Son bir uyarı: enine aramanın en kısa yol güvencesi, tüm kenarların eşit maliyetli sayılmasına dayanır. Kenarlara ağırlık eklendiği anda güvence ortadan kalkar ve kuyruk yerine öncelik kuyruğu gerekir; bu, ağaçlar konusundaki yığının çizge algoritmalarındaki rolünü açıklar. Ağırlıkların yalnızca bir bölümü farklıysa — örneğin bazı kenarlar sıfır, bazıları bir maliyetliyse — çift uçlu kuyrukla çalışan bir ara çözüm de kullanılabilir.

Özet

• Enine arama, kuyruk kullanarak başlangıçtan uzaklığa göre katman katman ilerler.
• Çizgede aynı düğüme birden çok yoldan ulaşılabildiği için ziyaret işaretlemesi zorunludur; işaretleme kuyruğa eklerken yapılır.
• Bulunan uzaklıklar, ağırlıksız çizgede en kısa yol uzunluklarıdır; güvence, kuyruğun ilk giren ilk çıkar davranışından gelir.
• Ebeveyn kayıtları tutulduğunda yolun kendisi geriye izlenerek kurulur.
• Maliyet, komşuluk listesiyle $O(V + E)$’dir; bellek en geniş katmana bağlıdır.
• Ağırlıklı çizgelerde enine arama yetmez; öncelik kuyruğu kullanan algoritmalar gerekir.

Sonraki Adım

Enine arama genişliği önceler: yakın olan her şey uzağa gitmeden gezilir. Karşıt strateji, bir yolu sonuna kadar izleyip ancak tıkandığında geri dönmektir. Sonraki ders bu stratejiyi ve onun çözdüğü farklı problem ailesini ele alacak.