--- title: 'Derine Arama' source: 'https://academia.sh/tr/kurslar/veri-yapilari/derine-arama' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:53+00:00' license: 'CC BY-SA 4.0' --- # Derine Arama Yığıtla derinlemesine gezinme, özyinelemeli ve açık yığıtlı biçimler, keşif–bitiş zamanları ve döngü tespiti. 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. ```python 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. ```python 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. ```python 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.