🏴‍☠️ LEYLA'S Code

🕸️ Ahoi du Graphen-Guru!

Stell dir vor, du stehst in einem riesigen Höhlensystem – jede Kammer verbunden mit anderen durch Gänge. Wie findest du den Ausgang? 🗺️

Aber warte mal... Es gibt zwei legendäre Strategien! BFS (Breadth-First Search) durchsucht erst alle Nachbar-Kammern, bevor es tiefer geht – wie Wellen im Wasser. DFS (Depth-First Search) stürzt sich sofort in die Tiefe – wie ein mutiger Taucher! 🏴‍☠️

🌐 Graphen überall!
Graphen sind mehr als nur Labyrinthe:
• Social Networks: Du → Freunde → Freunde der Freunde
  → "6 Degrees of Separation" via BFS!
• Google Maps: Städte → Straßen → Kürzester Weg
  → Dijkstra's Algorithmus basiert auf BFS
• Web Crawler: Webseite → Links → Alle erreichbaren Seiten
  → DFS crawlt das Internet!

💻 BFS vs. DFS Code:

# BFS - Nutzt QUEUE (FIFO) - "Breite zuerst"
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()  # Erste raus (FIFO)
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node])  # Alle Nachbarn hinzufügen
    
    return visited

# DFS - Nutzt STACK (LIFO) - "Tiefe zuerst"
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)  # Rekursion = impliziter Stack
    
    return visited

# Graph-Repräsentation (Adjacency List)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [], 'F': []
}

# BFS: A → B, C → D, E, F (Level für Level)
# DFS: A → B → D → E → C → F (Tiefe zuerst)

🎯 Deine Mission:
Ein Labyrinth voller Zyklen und Sackgassen! Nutze mark_visited(), um bereits besuchte Knoten zu markieren – sonst läufst du im Kreis! BFS findet den kürzesten Weg, DFS ist speicher-effizienter. Wähle weise!

⚡ Warum ist das wichtig?
Graph Traversal ist die Basis für:
• Routing-Algorithmen (GPS, Netzwerk-Pakete)
• Soziale Netzwerk-Analyse (Influencer finden)
• Compiler (Code-Abhängigkeiten auflösen)
• Game AI (Pathfinding in Spielen)
Jeder große Tech-Stack nutzt Graphen! 🏴‍☠️

╔══════════════════════════════════════════════════════════╗
║  BFS vs DFS - Graph Traversal Visualisierung          ║
╚══════════════════════════════════════════════════════════╝

  Graph-Struktur:
              A (Start)
            /   \\
          B       C
         / \\     |
        D   E   F

  ┌────────── BFS (Queue: FIFO) ───────────┐
  │ Level 0: [A]                         │
  │ Level 1: [B, C] ← Nachbarn von A    │
  │ Level 2: [D, E, F] ← Nachbarn v. B,C│
  │                                        │
  │ Queue: [A] → [B,C] → [C,D,E]      │
  │        → [D,E,F] → [E,F] → [F] → [] │
  │                                        │
  │ Besuchs-Reihenfolge: A → B → C → D → E → F │
  │ ✓ Findet KÜRZESTEN Weg!                │
  └─────────────────────────────────────────┘

  ┌────────── DFS (Stack: LIFO) ───────────┐
  │ Start: A → gehe zu B (erster Nachbar) │
  │ Von B → gehe zu D (erster Nachbar)    │
  │ D hat keine Nachbarn → backtrack zu B │
  │ Von B → gehe zu E (nächster Nachbar)  │
  │ E hat keine Nachbarn → backtrack zu A │
  │ Von A → gehe zu C (nächster Nachbar)  │
  │ Von C → gehe zu F → fertig!            │
  │                                        │
  │ Stack: [A] → [A,B] → [A,B,D]      │
  │        → [A,B] → [A,B,E] → [A]       │
  │        → [A,C] → [A,C,F] → []        │
  │                                        │
  │ Besuchs-Reihenfolge: A → B → D → E → C → F │
  │ ✓ Speicher-effizienter bei tiefen Graphen! │
  └─────────────────────────────────────────┘

  ⚡ Vergleich:
  BFS: O(V + E) Zeit, O(V) Space (Queue groß!)
  DFS: O(V + E) Zeit, O(h) Space (h = Höhe)
  (V = Vertices/Knoten, E = Edges/Kanten)

▶ 🤓 Für Code-Nerds: Noch tiefer eintauchen ⚓

🗺️ Graph-Repräsentationen:

# 1. ADJACENCY MATRIX (für dichte Graphen)
#    Space: O(V²) - gut für dichte Graphen
graph_matrix = [
    [0, 1, 1, 0],  # Knoten 0 verbunden mit 1, 2
    [1, 0, 0, 1],  # Knoten 1 verbunden mit 0, 3
    [1, 0, 0, 1],  # Knoten 2 verbunden mit 0, 3
    [0, 1, 1, 0]   # Knoten 3 verbunden mit 1, 2
]
# Vorteil: O(1) Edge-Check
# Nachteil: O(V²) Space auch bei wenigen Kanten

# 2. ADJACENCY LIST (für sparse Graphen)
#    Space: O(V + E) - gut für sparse Graphen
graph_list = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}
# Vorteil: Platzsparend, schnelle Nachbar-Iteration
# Nachteil: O(V) Edge-Check im Worst Case

# 3. EDGE LIST (für sehr sparse Graphen)
edges = [(0,1), (0,2), (1,3), (2,3)]
# Vorteil: Minimal Space
# Nachteil: Langsam für Traversal

🚀 Dijkstra's Algorithm (BFS-Variant):
Dijkstra findet den kürzesten Weg in gewichteten Graphen:

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # Priority Queue (distance, node)
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current_dist > distances[current]:
            continue
        
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# Dijkstra = BFS + Priority Queue (kleinste Distanz zuerst)
# Genutzt von: GPS Navigation, Routing-Protokolle (OSPF)

🎯 A* Algorithm (Optimierter Dijkstra):
A* kombiniert Dijkstra mit Heuristik für Gaming/Pathfinding:
• f(n) = g(n) + h(n)
• g(n) = tatsächliche Kosten von Start bis n
• h(n) = geschätzte Kosten von n bis Ziel (Heuristik)
→ Wird in Game Engines (Unity, Unreal) für Pathfinding genutzt!

🌐 BFS Anwendungen:
1. Shortest Path in Unweighted Graphs:
  → Maze Solving, Level Design in Games
2. Social Network Analysis:
  → "People You May Know" auf LinkedIn/Facebook
  → Berechne "Degrees of Separation"
3. Web Crawlers:
  → Google crawlt Webseiten Level für Level
4. Peer-to-Peer Networks:
  → BitTorrent findet Peers via BFS

🕷️ DFS Anwendungen:
1. Cycle Detection:
  → Finde Zyklen in Graphen (wichtig für Deadlock-Erkennung)
2. Topological Sorting:
  → Build Systems (Make, Gradle) ordnen Abhängigkeiten
3. Maze Generation:
  → Procedural Maze Generation in Games
4. Connected Components:
  → Finde zusammenhängende Regionen (z.B. in Bildern)

⚠️ Zyklus-Erkennung:

# DFS mit Zyklus-Erkennung
def has_cycle_dfs(graph, node, visited, rec_stack):
    visited.add(node)
    rec_stack.add(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle_dfs(graph, neighbor, visited, rec_stack):
                return True
        elif neighbor in rec_stack:  # Zurück zu Knoten im Stack!
            return True
    
    rec_stack.remove(node)  # Backtrack
    return False

# Genutzt in: Compiler (zirkuläre Abhängigkeiten), Deadlock-Erkennung

📊 Performance-Vergleich:
BFS:
• Zeit: O(V + E)
• Space: O(V) - Queue kann groß werden bei breiten Graphen
• Best für: Shortest Path, Level-Order Traversal

DFS:
• Zeit: O(V + E)
• Space: O(h) - nur Pfad-Höhe gespeichert
• Best für: Cycle Detection, Topological Sort, Memory-constrained

🏗️ Real-World Graphen:
• Facebook Social Graph: 3 Milliarden Knoten!
  → Nutzt optimiertes BFS für "Friend Suggestions"
• Google Maps: Millionen Kreuzungen
  → Dijkstra/A* für Navigation
• Internet-Routing: Milliarden Router
  → BGP nutzt modified Dijkstra
• Compiler-Optimierungen: Control Flow Graphs
  → DFS für Dead Code Elimination

🎓 Pro-Tipp:
• BFS mit Priority Queue = Dijkstra
• Dijkstra mit Heuristik = A*
• DFS mit Backtracking = Game Tree Search (Chess AI)
• BFS auf Bäumen = Level-Order Traversal
Die meisten Graph-Algorithmen sind Varianten von BFS/DFS! 🏴‍☠️

🚀 Next Level: Nach diesem Level verstehst du:
• PageRank (Google's Ranking-Algorithmus)
• Social Network Analysis (Influencer Detection)
• Game AI Pathfinding (A*, Navigation Meshes)
• Compiler Design (Control Flow Analysis)

Graphen sind überall - von sozialen Netzwerken bis zu neuronalen Netzen. Master BFS/DFS und du verstehst die Hälfte der modernen Informatik! - Deine Leyla 🐀

💡 Tipp: Monster sind chaotisch sortiert - nutze mark_visited() um Reihenfolge zu ändern!

🏴‍☠️ LEYLA'S CODE

Level 28 – Das Labyrinth-Netz

🏴‍☠️ Unterstütze Leyla's Code – Nutze meine Referral-Links!

🏴‍☠️ Spende BTC an Leyla's Code 🚀

🏴‍☠️ Level 28: Graph Traversal – BFS & DFS!

Was ist Graph Traversal?

Breadth-First-Search

Depth-First-Search