🔎 10.4: DFS (Depth-First Search)

Derinlik Öncelikli Arama - Dalları Sonuna Kadar Keşfetmek

📌 DFS Nedir?

DFS (Depth-First Search), bir grafı derinlemesine dolaşan bir algoritmadır. Bir yolu sonuna kadar takip eder, çıkmaza gelince geri döner ve başka yolları dener. Tıpkı bir labirentte ilerleme stratejisi gibi!

🧭 Labirent Benzetmesi

Bir labirentte kaybolduğunuzu düşünün. DFS stratejisi:

  1. Her zaman ileri git: Bir yol seç ve sonuna kadar ilerle
  2. Çıkmaza gelince geri dön: Son kavşağa kadar geri gel
  3. Başka yolu dene: Henüz denemediğin bir yol seç
  4. Tüm yollar denendi: Bir önceki kavşağa geri dön
📚

Stack Kullanır

LIFO: Son giren ilk çıkar

🔄

Recursive Doğası

Özyinelemeli çözüm doğal

🌲

Ağaç Benzeri

Dal dal keşfeder

⚙️ DFS Algoritması

🔄 Recursive (Özyinelemeli)

En doğal ve okunabilir yöntem. Call stack'i kullanır.

def dfs(node):
    if node visited: return
    mark node as visited
    process(node)
    for neighbor in node.neighbors:
        dfs(neighbor)

📚 Iterative (Stack ile)

Explicit stack kullanır. Derin graflarda stack overflow'u önler.

def dfs(start):
    stack = [start]
    while stack not empty:
        node = stack.pop()
        if node visited: continue
        mark as visited
        for neighbor in node.neighbors:
            stack.push(neighbor)

⚠️ BFS vs DFS Farkı

BFS = Queue (FIFO) → Seviye seviye yayılır

DFS = Stack (LIFO) → Derinlemesine dalar

🎮 İnteraktif DFS Animasyonu

DFS Adım Adım

Başlangıç düğümü: A

🎯 "Başlat" butonuna basarak DFS'i izleyin!

📚 Stack (Yığın)

Boş

✅ Ziyaret Sırası

-

🐍 Python Implementasyonu

DFS - Recursive Implementasyon 
def dfs_recursive(graph, start, visited=None):
    """
    DFS - Recursive (Özyinelemeli) Versiyon
    
    Bu yöntem call stack'i kullanır.
    Doğal ve okunabilir ama derin graflarda stack overflow olabilir.
    """
    if visited is None:
        visited = set()
    
    # Bu düğümü ziyaret et
    visited.add(start)
    print(f"Ziyaret: {start}")
    
    # Tüm komşuları recursive olarak ziyaret et
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited


# Test graf
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("Graf:")
for node, neighbors in graph.items():
    print(f"  {node}: {neighbors}")

print("\n=== DFS (Recursive) - A'dan Başlayarak ===\n")
visited = dfs_recursive(graph, 'A')

print(f"\n✅ Ziyaret edilen düğümler: {visited}")
Çıktı bekleniyor...
DFS - Iterative (Stack ile) Implementasyon 
def dfs_iterative(graph, start):
    """
    DFS - Iterative (Stack ile) Versiyon
    
    Explicit stack kullanır.
    Derin graflarda stack overflow'u önler.
    """
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()  # Stack'in tepesinden al (LIFO)
        
        if node in visited:
            continue
            
        visited.add(node)
        result.append(node)
        print(f"Ziyaret: {node}, Stack: {stack}")
        
        # Komşuları stack'e ekle (ters sırada ekleyerek alfabetik sırayı koruyoruz)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
                print(f"  → {neighbor} stack'e eklendi")
    
    return result


# Test
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("=== DFS (Iterative) - A'dan Başlayarak ===\n")
result = dfs_iterative(graph, 'A')

print(f"\n✅ Ziyaret sırası: {result}")
Çıktı bekleniyor...

🔄 Döngü Tespiti (Cycle Detection)

DFS'in en önemli uygulamalarından biri: grafta döngü olup olmadığını tespit etmek. Yönlü ve yönsüz graflar için farklı yaklaşımlar gerekir.

Döngü Tespiti - Yönsüz Graf 
def has_cycle_undirected(graph):
    """
    Yönsüz grafta döngü tespiti
    
    Mantık: Eğer ziyaret ettiğimiz bir komşu daha önce ziyaret edilmişse 
    VE parent'ımız değilse, döngü var demektir.
    """
    visited = set()
    
    def dfs(node, parent):
        visited.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):  # Recursive çağrı
                    return True
            elif neighbor != parent:
                # Ziyaret edilmiş ama parent değil = DÖNGÜ!
                print(f"  🔄 Döngü bulundu: {node} -> {neighbor}")
                return True
        
        return False
    
    # Tüm bileşenleri kontrol et
    for node in graph:
        if node not in visited:
            if dfs(node, None):
                return True
    
    return False


# Test 1: Döngüsüz graf (ağaç)
tree = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

print("=== TEST 1: Ağaç (Döngüsüz) ===")
print(f"Graf: {tree}")
print(f"Döngü var mı? {has_cycle_undirected(tree)}\n")

# Test 2: Döngülü graf
cyclic = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],  # B-C kenarı döngü oluşturur
    'C': ['A', 'B']
}

print("=== TEST 2: Döngülü Graf ===")
print(f"Graf: {cyclic}")
print(f"Döngü var mı? {has_cycle_undirected(cyclic)}")
Çıktı bekleniyor...
Döngü Tespiti - Yönlü Graf (DAG Kontrolü) 
def has_cycle_directed(graph):
    """
    Yönlü grafta döngü tespiti
    
    3 renk sistemi:
    - WHITE (0): Henüz ziyaret edilmedi
    - GRAY (1): Şu an ziyaret ediliyor (DFS stack'inde)
    - BLACK (2): Tamamen işlendi
    
    Eğer GRAY bir düğüme tekrar ulaşırsak = Döngü!
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    
    def dfs(node):
        color[node] = GRAY  # İşlemeye başladık
        
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:
                # GRAY düğüme ulaştık = Döngü!
                print(f"  🔄 Döngü: {node} -> {neighbor} (back edge)")
                return True
            if color[neighbor] == WHITE:
                if dfs(neighbor):
                    return True
        
        color[node] = BLACK  # Tamamen işlendi
        return False
    
    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return True
    
    return False


# Test 1: DAG (Döngüsüz Yönlü Graf)
dag = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print("=== TEST 1: DAG (Döngüsüz) ===")
print(f"Graf: {dag}")
print(f"Döngü var mı? {has_cycle_directed(dag)}\n")

# Test 2: Döngülü yönlü graf
cyclic = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A']  # C -> A döngü oluşturur
}

print("=== TEST 2: Döngülü Yönlü Graf ===")
print(f"Graf: {cyclic}")
print(f"Döngü var mı? {has_cycle_directed(cyclic)}")
Çıktı bekleniyor...

📐 Topological Sort (Topolojik Sıralama)

Topological Sort, bir DAG'daki (Directed Acyclic Graph) düğümleri öyle sıralar ki, her kenar u→v için, u her zaman v'den önce gelir. Görev planlaması için çok kullanışlı!

📚 Ders Ön Koşulları Örneği

Matematik → Fizik → Elektrik Mühendisliği

Topolojik sıralama, dersleri hangi sırada almanız gerektiğini söyler!

Topological Sort - DFS ile 
def topological_sort(graph):
    """
    DFS tabanlı Topolojik Sıralama
    
    Mantık: DFS'te bir düğümün tüm bağımlılıkları işlendikten sonra 
    o düğümü stack'e ekleriz. Sonunda stack'i ters çeviririz.
    """
    visited = set()
    result = []  # Stack olarak kullanılacak
    
    def dfs(node):
        visited.add(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        
        # Tüm bağımlılıklar işlendi, şimdi ekle
        result.append(node)
    
    # Tüm düğümleri ziyaret et
    for node in graph:
        if node not in visited:
            dfs(node)
    
    # Ters çevir (stack mantığı)
    return result[::-1]


# Ders ön koşulları örneği
courses = {
    'Matematik': ['Fizik', 'İstatistik'],
    'Fizik': ['Elektrik', 'Mekanik'],
    'İstatistik': ['Makine Öğrenmesi'],
    'Elektrik': ['Sinyal İşleme'],
    'Mekanik': [],
    'Makine Öğrenmesi': [],
    'Sinyal İşleme': []
}

print("=== DERS ÖN KOŞULLARI ===")
print("Graf (ders -> bağımlı dersler):")
for course, deps in courses.items():
    print(f"  {course}: {deps if deps else '(bağımlılık yok)'}")

print("\n=== TOPOLOJİK SIRALAMA ===")
order = topological_sort(courses)
print(f"Ders alma sırası: ")
for i, course in enumerate(order, 1):
    print(f"  {i}. {course}")
Çıktı bekleniyor...

📊 Karmaşıklık Analizi

Metrik Karmaşıklık Açıklama
Zaman O(V + E) Her düğüm 1 kez, her kenar 1 kez işlenir
Alan (Recursive) O(V) Call stack derinliği (en kötü: V)
Alan (Iterative) O(V) Explicit stack + visited set

🌍 Gerçek Dünya Uygulamaları

🧩 Labirent Çözme

Bir yolu sonuna kadar takip et, çıkmazsa geri dön. Klasik backtracking.

📦 Görev Planlaması

Topological sort ile bağımlılıkları çöz. Build sistemleri, CI/CD pipeline'lar.

🔄 Döngü Tespiti

Deadlock detection, circular import kontrolü, dependency cycle bulma.

🧬 Bağlantılı Bileşenler

Sosyal ağ kümeleri, görüntü segmentasyonu, network partitioning.

🎮 Oyun AI

Karar ağaçları, state space exploration, minimax algoritması.

🌐 Web Crawling

Derinlemesine sayfa tarama, sitemap oluşturma.

🆚 BFS vs DFS - Ne Zaman Hangisi?

Senaryo Tercih Neden?
En kısa yol (ağırlıksız) BFS Seviye sırasında arar, ilk bulunan en kısa
Döngü tespiti DFS Back edge kontrolü doğal
Topological sort DFS Post-order traversal kullanır
Yol var mı kontrolü Her ikisi İkisi de O(V+E), fark yok
Bellek kısıtlı ortam DFS O(h) vs O(V) bellek
Seviye analizi gerekli BFS Seviye bilgisi doğal olarak var