Derine Arama

Enine arama, uzaklığa göre ilerliyordu: yakın olan her şey gezilmeden uzağa gidilmiyordu. Derine arama (depth-first search) karşıt stratejiyi izler — bir yolu tıkanana kadar izler, sonra en son ayrım noktasına döner ve başka bir dal dener.

Yapısal fark tek bir yerdedir: kuyruk yerine yığıt kullanılır. Ağaçlarda seviye sıralı ve derinlik gezinmeleri arasındaki fark neyse, burada da odur.

Özyinelemeli Biçim

Yığıt açıkça tutulmayabilir; özyineleme, çağrı yığıtını aynı iş için kullanır.

def derine_ara(komsuluk: dict[str, list[str]], baslangic: str) -> list[str]:
    """Derinlemesine gezer; ziyaret sırasını döndürür."""
    ziyaret: set[str] = set()
    sira: list[str] = []

    def gez(dugum: str) -> None:
        ziyaret.add(dugum)
        sira.append(dugum)
        for komsu in komsuluk.get(dugum, []):
            if komsu not in ziyaret:
                gez(komsu)                       # tıkanana kadar derine in

    gez(baslangic)
    return sira


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

print(derine_ara(komsuluk, "bati"))
# ['bati', 'kuzey', 'merkez', 'guney', 'dogu']

Enine arama aynı çizgede ['bati', 'kuzey', 'guney', 'merkez', 'dogu'] sırasını veriyordu. Derine aramada kuzey düğümünden hemen merkez’e inilir; guney ancak o dal tükendiğinde ziyaret edilir.

Açık Yığıtlı Biçim

Programlama Temelleri kursunda kurulan dönüşüm burada da geçerlidir: çağrı yığıtı yerine açık bir yığıt tutulabilir. Derin çizgelerde bu, özyineleme sınırına çarpmayı önler.

def derine_ara_yigitla(komsuluk: dict[str, list[str]], baslangic: str) -> list[str]:
    ziyaret: set[str] = set()
    sira: list[str] = []
    yigit = [baslangic]
    while yigit:
        dugum = yigit.pop()                      # son giren ilk çıkar
        if dugum in ziyaret:
            continue
        ziyaret.add(dugum)
        sira.append(dugum)
        for komsu in reversed(komsuluk.get(dugum, [])):
            if komsu not in ziyaret:
                yigit.append(komsu)              # ters sırada it: sıra korunsun
    return sira


print(derine_ara_yigitla(komsuluk, "bati"))
# ['bati', 'kuzey', 'merkez', 'guney', 'dogu']

Komşuların ters sırada itilmesi, ağaç gezinmelerinde sağ çocuğun önce itilmesiyle aynı gerekçeye dayanır: yığıt, itilenlerin tersini verir.

İki biçim arasında ince bir fark vardır: açık yığıtlı sürümde bir düğüm, ziyaret edilmeden önce birden çok kez yığıta girebilir. Bu nedenle çıkarma sırasında yeniden denetlenir. Bellek kullanımı bir miktar artar, davranış aynı kalır.

Keşif ve Bitiş Zamanları

Derine aramanın taşıdığı ek bilgi, her düğüm için iki zaman damgasıdır:

• Keşif zamanı: Düğüme ilk ulaşıldığı an.
• Bitiş zamanı: Düğümün tüm soyu gezildikten sonra geri dönüldüğü an.

Bu iki değer, düğümler arasındaki ilişkiyi sınıflandırmayı sağlar. Bir düğümün keşif–bitiş aralığı, diğerinin aralığını tümüyle kapsıyorsa ikincisi birincinin soyudur; aralıklar kesişmiyorsa iki düğüm ayrı dallardadır. Aralıklar kısmen örtüşemez — bu, gezinmenin yığıt yapısının doğrudan sonucudur.

Bitiş zamanları, sonraki dersteki topolojik sıralamanın temelini oluşturur.

Döngü Tespiti

Derine aramanın en yaygın kullanımlarından biri, yönlü çizgede döngü aramaktır. Ayrım, “ziyaret edildi” ile “hâlâ yığıtta” arasındadır: gezinme sırasında hâlâ açık olan bir düğüme geri dönülüyorsa döngü vardır.

def dongu_var_mi(komsuluk: dict[str, list[str]]) -> bool:
    """Yönlü çizgede döngü olup olmadığını sınar."""
    ziyaret: set[str] = set()
    acik: set[str] = set()                       # o an yığıtta olanlar

    def gez(dugum: str) -> bool:
        ziyaret.add(dugum)
        acik.add(dugum)
        for komsu in komsuluk.get(dugum, []):
            if komsu in acik:
                return True                      # geri kenar: döngü
            if komsu not in ziyaret and gez(komsu):
                return True
        acik.discard(dugum)                      # dal tamamlandı
        return False

    return any(gez(d) for d in komsuluk if d not in ziyaret)


cevrimsiz = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
cevrimli = {"a": ["b"], "b": ["c"], "c": ["a"]}

print(dongu_var_mi(cevrimsiz))     # False
print(dongu_var_mi(cevrimli))      # True

acik kümesi olmadan, yalnızca ziyaret ile sınama yapılırsa yanlış sonuç alınır: cevrimsiz çizgesinde d düğümüne iki farklı yoldan ulaşılır, ama bu bir döngü değildir. İki kavramın ayrılması bu nedenle zorunludur.

İki Gezinmenin Karşılaştırması

Ölçüt	Enine arama	Derine arama
Yardımcı yapı	Kuyruk	Yığıt (veya özyineleme)
İlerleme	Katman katman	Dal boyunca derine
Ağırlıksız en kısa yol	Bulur	Bulmaz
Bellek	En geniş katman	En derin yol
Doğal kullanım	Uzaklık, yayılma, en az adım	Döngü, sıralama, geri izleme
Maliyet	$O(V + E)$	$O(V + E)$

Dördüncü satır pratik seçimde belirleyici olabilir: geniş ve sığ bir çizgede enine aramanın kuyruğu çok büyür; derin ve dar bir çizgede derine aramanın yığıtı.

Üçüncü satır ise en sık yapılan hatanın kaynağıdır: derine arama bir yol bulur, ama bulduğu yolun en kısa olduğuna dair hiçbir güvence yoktur.

Yinelemeli Derinleştirme

Karşılaştırma tablosu bir ikilem gösterir: enine arama en kısa yolu bulur ama belleği çok kullanabilir; derine arama az bellek kullanır ama en kısa yolu bulmaz.

Yinelemeli derinleştirme, ikisini birleştirir. Derine arama, önce derinlik sınırı bir olarak çalıştırılır; çözüm bulunamazsa sınır ikiye çıkarılır ve arama baştan yapılır. Sınır arttıkça derinleşilir.

İlk bakışta savurgan görünür — aynı üst katmanlar tekrar tekrar gezilir. Ancak dallanma çarpanı birden büyük olduğunda düğümlerin çoğu son katmandadır; tekrar edilen iş, toplamın küçük bir bölümü kalır. Maliyet, enine aramanınkiyle aynı mertebede olur.

Kazanç bellektedir: her an yalnızca tek bir yol yığıtta tutulur. Bulunan ilk çözüm de en sığ olanıdır, çünkü daha küçük sınırlarda çözüm bulunamamıştır.

Yöntem, arama uzayının önceden bilinmediği ve belleğe sığmadığı problemlerde — oyun ağacı araması, bulmaca çözme — tercih edilir.

Kullanım Alanları

• Döngü tespiti. Yukarıdaki gibi; bağımlılık çizgelerinin geçerliliği bu sınamayla denetlenir.
• Bağlı bileşenler. Enine aramada olduğu gibi, her ziyaret edilmemiş düğümden bir gezinme başlatılır.
• Topolojik sıralama. Bitiş zamanlarının tersi, geçerli bir sıralama verir; sonraki dersin konusu.
• Geri izleme. Labirent çözme, bulmaca doldurma ve kısıt sağlama problemleri, derine aramanın seçim ağacı üzerindeki uygulamasıdır.
• Yol bulma. İki düğüm arasında herhangi bir yol aranıyorsa — en kısası değil — derine arama daha az bellekle sonuç verir.

Özet

• Derine arama bir yolu tıkanana kadar izler, sonra son ayrım noktasına döner; kuyruk yerine yığıt kullanır.
• Özyinelemeli biçim çağrı yığıtını kullanır; açık yığıtlı biçim derin çizgelerde güvenlidir.
• Keşif ve bitiş zamanları düğümler arası soy ilişkisini kodlar; aralıklar ya kapsar ya ayrıktır.
• Döngü tespitinde “ziyaret edildi” ile “hâlâ açık” ayrımı zorunludur.
• Enine arama en kısa yolu bulur, derine arama bulmaz; bellek davranışları çizgenin biçimine göre ayrışır.
• İki gezinmenin de maliyeti $O(V + E)$’dir.

Sonraki Adım

Bağımlılık ilişkilerini modelleyen çizgelerde asıl soru şudur: işler hangi sırayla yapılmalıdır? Kursun son dersi, yönlü çevrimsiz çizgelerde geçerli bir yürütme sırası üreten topolojik sıralamayı ele alacak ve bu kursun kurduğu yapıları bir arada kullanacak.