--- title: 'Enine Arama' source: 'https://academia.sh/tr/kurslar/veri-yapilari/enine-arama' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:52+00:00' license: 'CC BY-SA 4.0' --- # Enine Arama Kuyrukla katman katman gezinme, ziyaret işaretleme, ağırlıksız en kısa yol ve yol geri kurma. 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 ```python 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: ```python 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. ```python 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.