Graflar: BFS ve DFS ile İlişkileri Gezinmek

İki kullanıcı arasında kaç arkadaşlık adımı olduğunu veya bir paketin hangi bağımlılıklara ihtiyaç duyduğunu bulmak istiyoruz. Bu ilişkiler basit bir hiyerarşi değildir; bir öğe birçok öğeye bağlanabilir. Graph modeli bu problemi temsil eder.

Graph nedir?

Vertex/node varlığı, edge iki varlık arasındaki bağlantıyı temsil eder. Directed graph’ta kenarın yönü vardır; weighted graph’ta kenar maliyet taşır. Cycle, bir düğümden başlayıp tekrar ona dönen yoldur.

Adjacency list (komşuluk listesi) her düğüm için yalnızca bağlı olduğu komşuları saklar ve bağlantı sayısı olası bağlantılardan çok az olan seyrek graflarda verimlidir. Adjacency matrix (komşuluk matrisi) bütün olası düğüm çiftlerini tabloya koyar; iki düğüm arasında kenar kontrolü hızlıdır fakat V düğüm için V × V, yani O(V²) alan kullanır.

BFS ne yapar?

Breadth-first search başlangıç düğümüne en yakın seviyeyi önce gezer ve queue kullanır. Ağırlıksız grafta en az kenarlı yolu bulabilir.

queue.push(start);
visited.add(start);

while (queue.length > 0) {
  const current = queue.shift()!;
  for (const neighbor of graph.get(current) ?? []) {
    if (!visited.has(neighbor)) {
      visited.add(neighbor);
      queue.push(neighbor);
    }
  }
}

visited, cycle yüzünden aynı düğümün sonsuza kadar işlenmesini önler. Komşu kuyruğa eklenirken visited işaretlemek, aynı düğümün birden çok kez sıraya girmesini engeller.

DFS ne yapar?

Depth-first search bir dalda ilerleyebildiği kadar ilerler; recursion veya açık stack kullanır. Cycle tespiti, topological sort ve bağlı bileşen keşfinde kullanılır. Çok derin grafta recursion stack taşabilir; iteratif DFS daha güvenlidir.

Alternatifler

Ağırlıklar negatif değilse en düşük maliyetli yol için Dijkstra, negatif kenarlar için Bellman–Ford, hedefe yönelik sezgisel arama için A* kullanılabilir. BFS yalnızca her kenarın maliyeti eşit kabul edildiğinde en kısa yolu garanti eder.

Alıştırma

Beş şehir ve yollarından küçük bir graph oluşturun. BFS ile en az aktarmalı rotayı bulun; sonra bir yol maliyeti ekleyince neden BFS’nin artık en ucuz rotayı garanti etmediğini açıklayın.