Şöyle ki, Graph deyince aklıma ilk gelen şey “kısa yol” oluyor — sanırım çoğunuzda da öyle. BFS, yani Breadth-First Search, tam da bu işlerde devreye giriyor. Dışarıdan bakınca basit, neredeyse trivial bile. Ama uygulamaya girince… hmm, ufak bir hata her şeyi alt üst edebiliyor (ciddiyim). Ben bunu 2017 yazında Kadıköy’de bir fintech projesinde ilk kez graph traversal yazarken çok net hissettim: kuyruk doğru çalışmadı mı, sonuçlar kayıyor. Debug işe uzayıp gidiyor. Uzayıp gidiyor ya da gidip gidiyor.
Bu yazıda BFS’i Java üzerinden anlatacağım — lafı gevelemeden ama kuru da olmadan. Hedef şu: hem yeni başlayan biri “tamamdır, mantığı kaptım” desin, hem de biraz deneyimli olan biri edge case tarafında neye dikkat etmesi gerektiğini görsün. Çünkü BFS kağıt üstünde tertemiz duruyor… pratikte işe visited kontrolü unutulursa işler hızla çorbaya dönüyor.
BFS Mantığı: En Yakındaki Düğümden Başlamak
BFS’in benim en sevdiğim tarafı şu: karmaşık bir sorunu katman katman açıyor (şaşırtıcı ama gerçek). Önce başlangıç düğümüne en yakın olanları geziyor, sonra bir sonraki halkaya geçiyor. Metro haritası gibi düşünün; önce bulunduğunuz durağa yakın istasyonlar, sonra onların komşuları, sonra daha uzaktakiler. Güzel analoji değil mi?
Ve işler burada ilginçleşiyor.
Bence, DFS ile karıştıran çok oluyor. Tabi ki. DFS daha çok bir tünele dalar gibi ilerlerken, BFS genişliğe yayılıyor — sanki su yüzeyine düşen bir taşın yarattığı daireler gibi, merkezdeki noktadan dışa doğru eşit mesafelerde büyüyen halkalar (evet, doğru duydunuz). Bu yüzden kısa yol arıyorsanız çoğu senaryoda ilk aday BFS oluyor,. Hemen şunu da ekleyeyim: ağırlıklı grafikte tek başına mucize beklemeyin, orada iş değişiyor, başka araçlara ihtiyaç duyuyorsunuz (ben de ilk duyduğumda şaşırmıştım)
Geçen sene Şişli’de küçük bir e-ticaret yan projesinde ürün öneri grafiğiyle oynarken bunu yeniden gördüm. “Yakın bağlantılar” üzerinden öneri çıkarırken BFS gayet iş gördü. Fakat grafik büyüyünce bellek kullanımı tatlı tatlı kabarmaya başladı (en azından benim deneyimim böyle). Yani algoritma iyi. Ama veri büyüyünce tablo değişiyor.
Kuyruk Neden Bu Kadar Önemli?
Küçük bir detay: BFS’in kalbi kuyruk. Nokta.
Bence, FIFO mantığıyla çalışıyor: önce gelen önce çıkıyor. Böylelikle seviyeleri düzgün şekilde geziyorsunuz. Peki bunu neden söylüyorum? Eğer stack kullanırsanız — evet, o meşhur karışıklık — bu kez DFS’e kayarsınız ve bütün o güzel düzen bir anda bozulur, üstelik neden bozulduğunu anlamak da zaman alır.
Bunu 2020’nın sonlarında Ankara’daki bir eğitim oturumunda özellikle örneklemiştim. Öğrencilerden biri kuyruk yerine listeyi sondan çekerek denemişti; kod çalıştı, hata vermedi,. Davranış tamamen farklı çıktı. O an yüz ifadesini hatırlıyorum… hani “neden aynı şey olmadı?” bakışı vardır ya, tam öyle. Bir şeyler çalışıyor ama yanlış çalışıyor — bu aslında en sınır bozucu hata türü.
Java’da BFS Nasıl Yazılır?
Java tarafında iş oldukça düz gidiyor: Queue, LinkedList ya da bazen ArrayDeque (şaşırtıcı ama gerçek). Açık konuşayım — modern Java’da çoğu durumda ArrayDeque daha tatlı çalışıyor, gerçekten. Ama örnek anlatırken LinkedList görmek yeni başlayan için daha tanıdık geliyor, arayüzle olan ilişkisi daha okunabilir hissettiriyor, o yüzden burada önü kullanacağım.
Hmm, bunu nasıl anlatsamdı… Daha fazla bilgi için İlk Satırdan Fazlası: Küçük Bir Selamın Büyük Hikâyesi yazımıza bakabilirsiniz.
Bunu yaşayan biri olarak söyleyeyim, Aşağıdaki iskelet yapı basit ama iş görüyor. Düğümü ziyaret ediyoruz, komşuları kuyruğa atıyoruz, tekrar girişleri engelliyoruz. İlginç, değil mi? Hani şu “bir kez görünce not al, bir daha bakma” mantığı var ya — BFS tam olarak önü yapıyor (buna dikkat edin) TypeScript Utility Type’ları: SaaS’ta Gerçekten İşe Yarayanlar yazımızda bu konuya da değinmiştik.
import java.util.*;
class Node {
int value;
List<Node> neighbors = new ArrayList<>();
boolean visited = false;
Node(int value) {
this.value = value;
}
}
public class BFSExample {
public static void traverse(Node root) {
Queue<Node> queue = new LinkedList<>();
root.visited = true;
queue.add(root);
while (!queue.isEmpty()) {
Node current = queue.poll();
System.out.println(current.value);
for (Node neighbor : current.neighbors) {
if (!neighbor.visited) {
neighbor.visited = true;
queue.add(neighbor);
}
}
}
}
}Kodun içinde kritik nokta şu: visited bayrağını komşuyu kuyruğa eklerken set ediyorsunuz. Eğer poll ettikten sonra yaparsanız bazı döngülü graph’larda aynı node iki, üç kere sıraya girebilir. Küçük testte belli olmaz. Üretimde işe pat diye çıkar — tam en kötü zamanda.
Bak şimdi, Bir de şunu söyleyeyim: tree yapısında iş nispeten rahat ilerliyor çünkü parent-child ilişkisi daha temiz, daha öngörülebilir oluyor. Graph tarafında işe aynı node’a birden fazla yoldan ulaşabildiğiniz için disiplin şart, yoksa algoritma güzel çalışıyor gibi görünüp arka planda sessizce yanlış sonuçlar üretebiliyor. Daha fazla bilgi için iPad Air 11 (M4): Fiyatına Göre İyi mi, Fazla mı İddialı? yazımıza bakabilirsiniz. BFF Nedir? Frontend İçin Akıllı Orta Katman Rehberi yazımızda da bu konuya değinmiştik. React’te Dosya Yükleme: Sürükle-Bırak ve Önizleme yazımızda da bu konuya değinmiştik.
Küçük Bir Örnekle Adım Adım Gidelim
| Düğüm | Sıradaki Komşular | Kuyruk Durumu | Ziyaret Sırası |
|---|---|---|---|
| A | B, C | B, C | A |
| B | D, E | C, D, E | A → B |
| C | F | D, E, F | A → B → C |
| D/E/F | – | – | A → B → C → D → E → F |
Böyle bakınca olayın özü netleşiyor aslında. Önce ilk halka bitiyor, sonra ikinci halka geliyor. Algoritmanın ritmi bozuk değil — oldukça düzenli, hatta biraz disiplinli bile diyebilirim. Neredeyse takıntılı derecede sıralı.
Nerelerde İşe Yarıyor?
BFS’i sadece akademik alıştırma sanmayın. Web crawler yazarken linkleri seviye seviye taramak istiyorsanız burada güzel çalışır. Sosyal ağlarda “iki kişi arasında en kısa bağ nedir?” sorusu da yine buraya göz kırpar. Ağ topolojisi keşfi yapan araçlarda da sıkça karşınıza çıkar — yani sektörde gerçekten kullanılıyor bu şey.
Ben 2023 başında İzmir’de bir kurumsal iç ağ analizi sırasında benzer mantığı kullandım. Ama orada küçük bir sürpriz vardı: grafik sandığımızdan çok daha yoğundu. Tüm node’ları RAM’e almak pahalıya geldi, beklenmedik bir şekilde. İşte burada küçük startup ile enterprise arasındaki fark ortaya çıkıyor — startup için sorunsuz çalışan şey kurumsal ölçekte tıkanabiliyor, bazen de tamamen çöküyor.
- Kısa yol bulma senaryoları için çok uygun.
- Katman bazlı gezinme gerektiğinde temiz çözüm veriyor.
- Döngülü graph’larda visited yönetimi şart oluyor.
- Büyük veri setlerinde bellek tüketimine dikkat etmek gerekiyor.
- Ağırlıklı yollar için tek başına yeterli olmayabilir. — bunu es geçmeyin
- Tamamıyla doğru kurgu yapılmazsa sonsuz döngü riski doğar.
- Düzensiz veri yapılarında debug süresi uzayabilir…
Küçük Startup mı, Kurumsal Sistem mi?
Küçük bir startup’ta BFS genelde hızlı prototip çıkarmak için şahane iş görür. Mesela kullanıcı ilişkileri veya içerik öneri sistemi gibi alanlarda birkaç bin node varsa konu büyük ölçüde hallolur, ekstra mimarı kurmanıza gerek kalmaz.
E tabi kurumsal tarafta tablo değişiyor. Milyonlarca bağlantı varsa sadece algoritma değil veri modeli de önem kazanıyor — graph veritabanı mı kullanacaksınız, cache koyacak mısınız, traversal derinliği sınırı olacak mı? Bunlar yoksa elinizdeki o güzel fikir gece yarısı sızı uyutmuyor, inanın (eh, fena değil)
BFS basit görünür ama asıl mesele kodu yazmak değil; visited stratejisini doğru seçmek ve veriyi taşıyabilecek mimariyi kurmaktır.
Sık Yapılan Hatalar ve Ufak Tuzaklar
En klasik hata visited kontrolünü unutmak. İkinci klasik hata işe kuyruğa ekleme sırasını bozmak ya da yanlış veri yapısı seçmek oluyor. Bir de şu var: graph disconnected işe yalnızca root’tan erişilebilen kısmı gezersiniz; geri kalan adalar olduğu yerde kalır, siz de “neden bazı düğümlere hiç ulaşamıyorum?” diye saatlerce bakarsınız koda.
Ters Köşe Eden Noktalar
Sıkça Sorulan Sorular
BFS hangi durumda en iyi seçimdir?
BFS, grafikte kenarlar ağırlıksızsa ve “en az kenar sayısıyla” en kısa yolu arıyorsanız çok iyi çalışır. Başlangıçtan itibaren katman katman gittiği için ilk ulaştığı hedef düğüm genelde en kısa mesafeyi temsil eder. Ağırlıklı grafikte işe tek başına BFS doğru sonuç vermez; başka algoritmalar devreye girer.
BFS’te visited kontrolü ne zaman yapılmalı?
Genelde visited kontrolünü “kuyruğa eklerken” yapmak en sağlıklısıdır. Böylece aynı düğüm birden fazla kez kuyruğa düşmez ve gereksiz iş yükü oluşmaz. Ben bir projede visited’i çıktıktan sonra kontrol edince kuyruk şişti; sonuçlar doğruydu ama performans gereksiz yere düştü.
BFS ile en kısa yolu nasıl geri çıkarırım?
Mesafe için genelde bir distance ya da seviye mantığı tutulur; yol için işe parent (öncül) bilgisi saklanır. Hedefe ulaştığınızda parent zincirini geriye doğru izleyip yolu yeniden kurarsınız. Bu yaklaşım, “sadece uzunluğu bulmak” yerine “gerçek rotayı” da vermek için pratik.
Graf yönlü mü yönsüz mü fark eder mi?
Fark eder; çünkü komşulukları nasıl tanımladığınıza göre BFS’in ulaşabildiği düğümler değişir. Yönlü grafikte bir kenarın ters yönü otomatik olarak yoktur, o yüzden “komşu” listesini doğru üretmek kritik. Yanlış komşuluk üretince BFS düzgün çalışsa bile beklediğiniz düğümlere ulaşamazsınız.
BFS’in zaman ve bellek karmaşıklığı nedir?
Standart bir BFS, zaman olarak O(V + E) çalışır; çünkü her düğüm ve her kenar bir şekilde işlenir. Bellek tarafında da kuyruk ve visited/mesafe dizileri devreye girer; bu yüzden graf büyüdükçe bellek kullanımı artar. Ben özellikle büyük veri grafiğinde “komşu listesi” yapısını optimize etmenin fark yarattığını görmüştüm.
Kaynaklar ve İleri Okuma
Queue
Azure mimarilerinde Graph yaklaşımı — Microsoft Learn
Breadth-First Search (BFS) — Wikipedia
20+ yıl deneyimli Azure Solutions Architect. Microsoft sertifikalı bulut mimari ve DevOps danışmanı. Azure, yapay zekâ ve bulut teknolojileri üzerine Türkçe teknik içerikler üretiyor.
İlgili Yazılar
Bu içerik işinize yaradı mı?
Benzer içerikleri kaçırmamak için beni sosyal medyada takip edin.
