Graphen und Bäume

Graphen und Bäume sind fundamentale Datenstrukturen, die wir für Suchalgorithmen wie BFS und DFS benötigen.

Grundlagen

Knoten (Nodes/Vertices)

Ein Knoten ist ein Element im Graph. In Suchproblemen repräsentiert ein Knoten einen Zustand.

Beispiel: In einem Labyrinth ist jeder Knoten eine Position (x, y).

Kanten (Edges)

Eine Kante verbindet zwei Knoten und repräsentiert eine Aktion oder einen Übergang zwischen Zuständen.

Beispiel: In einem Labyrinth verbindet eine Kante zwei benachbarte Positionen, wenn man von einer zur anderen gehen kann.

A --- B
|     |
C --- D

Hier sind A, B, C, D Knoten und die Linien sind Kanten.

Bäume

Ein Baum ist ein spezieller Graph mit folgenden Eigenschaften:

• Azyklisch: Es gibt keine Zyklen (keine geschlossenen Pfade)
• Zusammenhängend: Alle Knoten sind durch Pfade verbunden
• Genau ein Wurzelknoten: Ein Knoten ohne Eltern
• Jeder andere Knoten hat genau einen Elternknoten

Kinder (Children)

In einem Baum hat jeder Knoten (außer den Blättern) Kinder - das sind die Knoten, die direkt unter ihm liegen.

    A (Wurzel)
   / \
  B   C
 / \
D   E

Hier ist:

• A ist die Wurzel
• B und C sind Kinder von A
• D und E sind Kinder von B
• D und E sind Blätter (haben keine Kinder)

Baum traversieren

Traversieren bedeutet, alle Knoten eines Baumes systematisch zu besuchen. Es gibt verschiedene Strategien:

• Breitensuche (BFS): Besuche zuerst alle Knoten auf einer Ebene, dann die nächste Ebene
• Tiefensuche (DFS): Gehe so tief wie möglich in einen Zweig, bevor du zurückgehst

Zyklisch vs. Azyklisch

Azyklisch

Ein Graph ist azyklisch, wenn es keine geschlossenen Pfade gibt. Du kannst nicht von einem Knoten ausgehen und wieder zu ihm zurückkommen.

A → B → C
     ↓
     D

Dieser Graph ist azyklisch.

Zyklisch

Ein Graph ist zyklisch, wenn es geschlossene Pfade gibt.

A → B → C
↑       ↓
D ← E ← F

Hier gibt es Zyklen (z.B. A → B → C → F → E → D → A).

Wichtig für Suche: Bei zyklischen Graphen müssen wir verfolgen, welche Knoten wir bereits besucht haben, um Endlosschleifen zu vermeiden.

Gewichtet vs. Ungewichtet

Ungewichtet

In einem ungewichteten Graph haben alle Kanten die gleiche "Kosten" oder "Distanz".

A --- B --- C

Jede Kante zählt gleich (z.B. 1 Schritt).

Gewichtet

In einem gewichteten Graph haben Kanten unterschiedliche Kosten.

A --5-- B --3-- C

Die Kante A→B kostet 5, die Kante B→C kostet 3.

Beispiel: In einem Straßennetz könnten die Gewichte die Entfernung oder Fahrzeit zwischen Städten sein.

Zielzustand

Ein Zielzustand ist der Zustand, den wir erreichen wollen. Im Graph ist das ein spezieller Knoten.

Beispiel: In einem Labyrinth ist der Zielzustand die Position des Ausgangs.

Bei Suchalgorithmen prüfen wir bei jedem besuchten Knoten, ob es der Zielzustand ist.

Graph-Darstellung im Code

Adjazenzliste

Eine Adjazenzliste speichert für jeden Knoten eine Liste seiner Nachbarn:

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

Für Labyrinth (2D-Gitter)

Bei einem Labyrinth können wir Nachbarn dynamisch berechnen:

def hole_nachbarn(labyrinth, x, y):
    """Gibt alle passierbaren Nachbarn einer Position zurück"""
    nachbarn = []
    richtungen = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # rechts, links, unten, oben
    
    for dx, dy in richtungen:
        nx, ny = x + dx, y + dy
        if ist_passierbar(labyrinth, nx, ny):
            nachbarn.append((nx, ny))
    
    return nachbarn

Zusammenfassung für BFS/DFS

Um BFS und DFS zu verstehen und anzuwenden, brauchst du:

1. Knoten verstehen: Jeder Knoten = ein Zustand
2. Kanten verstehen: Jede Kante = eine mögliche Aktion
3. Kinder finden: Von einem Knoten zu seinen Nachbarn gehen
4. Zyklische Graphen erkennen: Besuchte Knoten markieren, um Endlosschleifen zu vermeiden
5. Zielzustand prüfen: Bei jedem besuchten Knoten prüfen, ob es das Ziel ist
6. Gewichtete vs. ungewichtete: Für BFS/DFS zunächst ungewichtet (alle Schritte zählen gleich)

Mit diesem Wissen kannst du BFS und DFS auf jedem Graph oder Baum anwenden!