Graphen.

Ein Graph ist eine Menge von Knoten, die durch Kanten verbunden sind. Formal: G = (V, E) mit V als Knotenmenge und E als Kantenmenge. Praktisch modellierst du damit alles, was Beziehungen hat: Straßennetz, soziale Netzwerke, Web-Links, Abhängigkeiten zwischen Vorlesungen. Du lernst hier den Unterschied zwischen gerichtet vs ungerichtet, gewichtet vs ungewichtet, die zwei Standard-Repräsentationen Adjazenzmatrix (O(V²) Speicher) vs Adjazenzliste (O(V+E) Speicher), die zwei wichtigsten Traversierungs-Algorithmen BFS (Queue-basiert, kürzeste Pfade in ungewichteten Graphen) und DFS (Stack/Rekursion-basiert, topologische Sortierung in DAGs), den Dijkstra-Algorithmus für kürzeste Pfade in gewichteten Graphen (nur bei nicht-negativen Kanten; bei negativen Kanten Bellman-Ford verwenden) und die Euler-/Hamilton-Pfad-Charakterisierungen.

Die zentralen Konzepte für die Klausur:

• Gerichtet vs ungerichtet: hat eine Kante eine Richtung (z.B. Twitter-Follow) oder nicht (z.B. Facebook-Freundschaft)
• Gewichtet vs ungewichtet: haben Kanten Werte (z.B. Entfernung in km) oder nicht
• Adjazenzmatrix vs Adjazenzliste: Matrix braucht O(V²) Speicher, Liste nur O(V+E), dafür ist Lookup teurer
• BFS (Breitensuche) mit Queue: liefert kürzeste Pfade in ungewichteten Graphen
• DFS (Tiefensuche) mit Stack/Rekursion: gut für Zyklen-Erkennung und topologische Sortierung
• Dijkstra: kürzester Weg in gewichteten Graphen mit nicht-negativen Kanten

In Klausuren wirst du oft gefragt: gegeben ein Graph, traversiere ihn mit BFS oder DFS und gib die Reihenfolge der besuchten Knoten an. Lerne den Pseudocode, nicht nur die Idee.

Das Problem

• Google Maps: kürzester Weg von Berlin nach München?
• Facebook: zeig mir Freunde von Freunden
• Web: alle Seiten erreichbar von startseite.de
• Stundenplan: kann ich Vorlesung A, B, C zeitlich kombinieren?

Alles Graph-Probleme. Kein anderes Datenstruktur-Konzept hat so viele Anwendungen.

Die Definition

Ein Graph G = (V, E) besteht aus einer Menge Knoten V (vertices) und einer Menge Kanten E (edges) zwischen diesen Knoten.

       A ─── B ─── C
       │     │     │
       D ─── E ─── F
             │   ╱
             G ─╱

V = {A, B, C, D, E, F, G} E = {AB, AD, BC, BE, CF, DE, EF, EG, FG}

Vier Arten von Graphen

Klausur-Klassiker: zuerst klären, was für ein Graph vorliegt. Algorithmen reagieren unterschiedlich.

Wie wird ein Graph gespeichert?

Zwei Standard-Repräsentationen:

Adjacency Matrix

Eine n × n-Matrix mit 0/1 (oder Gewichten):

    A  B  C  D  E  F  G
 A [0  1  0  1  0  0  0]
 B [1  0  1  0  1  0  0]
 C [0  1  0  0  0  1  0]
 D [1  0  0  0  1  0  0]
 E [0  1  0  1  0  1  1]
 F [0  0  1  0  1  0  1]
 G [0  0  0  0  1  1  0]

• ✅ O(1) Existenz-Check "ist Kante AB drin?"
• ✅ Bei dichten Graphen oft sinnvoll, weil E nahe V² liegt und O(1)-Kantenchecks möglich sind
• ❌ O(V²) Speicher, auch wenn nur wenige Kanten gesetzt sind
• ❌ Iterieren über Nachbarn: O(V)

Adjacency List

Pro Knoten eine Liste der Nachbarn:

A → [B, D]
B → [A, C, E]
C → [B, F]
D → [A, E]
E → [B, D, F, G]
F → [C, E, G]
G → [E, F]

• ✅ O(V + E) Speicher, sparsam bei wenigen Kanten
• ✅ Iterieren über Nachbarn: O(grad(v))
• ❌ Existenz-Check langsamer: O(grad(v))

Bei ungerichteten Graphen wird jede Kante in der Standard-Adjazenzlisten-Implementierung zweimal gespeichert (einmal in jeder Endpunkt-Liste), damit Nachbar-Iteration von beiden Enden funktioniert. Asymptotisch bleibt der Speicher O(V+E).

Faustregel: bei sparsen Graphen (E ll V²) Adjacency List, bei dichten Adjacency Matrix.

Matrix vs Liste: Vergleich auf einen Blick

BFS, Breadth-First Search (Ebenenweise)

Geht schichtweise durch den Graph: erst alle direkten Nachbarn, dann deren Nachbarn, usw.

function BFS(start):
    visited = {start}
    queue = [start]
    while queue not empty:
        node = queue.pop_front()        // Queue: FIFO
        print(node)
        for neighbor in adjacency[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.push_back(neighbor)

Datenstruktur: Queue (FIFO).

Beispiel auf dem Graph oben, Start A:

Schritt 1: Queue [A] → besuche A → Nachbarn B, D dazu
Schritt 2: Queue [B, D] → besuche B → Nachbarn C, E dazu
Schritt 3: Queue [D, C, E] → besuche D
Schritt 4: Queue [C, E] → besuche C → Nachbar F dazu
Schritt 5: Queue [E, F] → besuche E → Nachbar G dazu
Schritt 6: Queue [F, G] → besuche F
Schritt 7: Queue [G] → besuche G

Reihenfolge: A, B, D, C, E, F, G

Pfad-Eigenschaft: BFS findet kürzeste Wege nach Anzahl der Kanten in ungewichteten Graphen, sofern der Zielknoten erreichbar ist.

Komplexität (Adjazenzliste): O(V + E), jeder Knoten wird einmal besucht, jede Kante höchstens konstant oft betrachtet (bei ungerichteten Graphen einmal pro Endpunkt). Mit Adjazenzmatrix wird BFS/DFS typischerweise O(V²), weil pro Knoten alle möglichen Nachbarn geprüft werden.

DFS, Depth-First Search (in die Tiefe)

Geht so tief wie möglich, dann zurück.

function DFS(start):
    visited = {start}
    stack = [start]
    while stack not empty:
        node = stack.pop()              // Stack: LIFO
        print(node)
        for neighbor in adjacency[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.push(neighbor)

Oder rekursiv (eleganter):

function DFS(node, visited):
    if node in visited: return
    visited.add(node)
    print(node)
    for neighbor in adjacency[node]:
        DFS(neighbor, visited)

Datenstruktur: Stack (LIFO) oder Rekursion (System-Stack).

Beispiel Graph oben, Start A (Nachbarn alphabetisch besucht):

Stack [A] → besuche A, push D, B (umgekehrt!) → Stack [D, B]
Stack [D, B] → pop B → besuche B, push E, C → Stack [D, E, C]
Stack [D, E, C] → pop C → besuche C, push F → Stack [D, E, F]
... → A, B, C, F, E, D, G

Achtung Reihenfolge: damit beim iterativen Stack-DFS die Nachbarn alphabetisch besucht werden, müssen sie in umgekehrter Reihenfolge gepusht werden, der zuletzt gepushte wird zuerst gepoppt.

Pfad-Eigenschaft: DFS ist NICHT für kürzeste Pfade. Aber super für: Zyklen finden, topologisches Sortieren, Zusammenhangskomponenten.

Komplexität (Adjazenzliste): O(V + E), wie BFS. Mit Adjazenzmatrix: O(V²).

BFS vs. DFS, wann was?

Faustregel: "kürzester Pfad" → BFS. "alle Pfade", "Zyklus", "Sortierung" → DFS.

Kürzester Pfad: Dijkstra (Bonus)

Bei gewichteten Graphen reicht BFS nicht. Dijkstra löst das.

function Dijkstra(start, target):
    dist[start] = 0; dist[other] = ∞
    pq = priority_queue([(0, start)])     // Min-Heap nach Distanz
    while pq not empty:
        (d, node) = pq.pop_min()
        if d > dist[node]: continue       // veralteter PQ-Eintrag, überspringen
        if node == target: return d
        for (neighbor, weight) in adjacency[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                pq.push((new_dist, neighbor))

Der if d > dist[node] Check filtert veraltete PQ-Einträge, wenn ein Knoten schon mit einer besseren Distanz expandiert wurde, übersprungen wir den alten Eintrag. Ohne diesen Check wird derselbe Knoten möglicherweise mehrfach aus der PQ gepoppt (wenn mehrere Distanz-Updates in der PQ landen), was die Laufzeit verschlechtert, aber die Korrektheit bei nicht-negativen Gewichten nicht verletzt.

Dijkstra braucht eine Priority Queue (Min-Heap) als Datenstruktur. Komplexität: O((V + E) log V).

Achtung: Dijkstra funktioniert NUR mit nicht-negativen Gewichten. Bei negativen Kanten → Bellman-Ford.

Wichtige Eigenschaften

Zusammenhängend:

• Ungerichtet: jeder Knoten kann jeden anderen erreichen. (Bei BFS/DFS von einem Start: wenn am Ende alle Knoten besucht sind, ist der Graph zusammenhängend.)
• Gerichtet: man unterscheidet stark zusammenhängend (jeder erreicht jeden über gerichtete Wege) und schwach zusammenhängend (der zugrunde liegende ungerichtete Graph ist zusammenhängend).

Zyklus: ein geschlossener Pfad, der zum Start zurückkehrt, typischerweise mit mindestens einer Kante, ohne zwischendurch Knoten zu wiederholen. In gerichteten Graphen müssen alle Kantenrichtungen eingehalten werden. DFS erkennt Zyklen, wenn ein bereits besuchter Knoten im aktuellen Pfad erreicht wird.

Baum (für ungerichtete Graphen): zusammenhängend und azyklisch. Mit n Knoten genau n-1 Kanten. (Für gerichtete Bäume / Arboreszenzen gelten andere Definitionen.)

Bipartit: Knoten lassen sich in zwei Mengen teilen, Kanten gehen nur zwischen den Mengen. BFS findet das mit 2-Färbung.

Grad eines Knotens: Anzahl Kanten, die ihn berühren. Bei gerichteten Graphen: Eingangsgrad und Ausgangsgrad.

Klausur-Tricks

Trick 1, Datenstruktur immer angeben: BFS = Queue, DFS = Stack/Rekursion. In Klausur immer dazu sagen.

Trick 2, Reihenfolge bei DFS ist nicht eindeutig. Wenn die Aufgabe DFS verlangt, gib die Nachbar-Reihenfolge an (üblich: alphabetisch oder ID-aufsteigend).

Trick 3, Visited-Set vergessen = Endlosschleife. Beim Erkunden eines Graphen IMMER markieren, welche Knoten schon besucht wurden.

Trick 4, Komplexität BFS / DFS hängt von der Repräsentation ab:

• Adjazenzliste: O(V + E), Klausur-Standard.
• Adjazenzmatrix: O(V²), pro Knoten alle möglichen Nachbarn prüfen.

Trick 5, Adjacency-Matrix vs. Liste:

• Matrix: gut bei dichten Graphen oder häufigen "ist Kante drin?"-Checks. Speicher O(V²).
• Liste: gut bei sparsen Graphen. Speicher O(V + E).

Trick 6, Wege zählen: Anzahl der Kanten in einem Pfad. Bei BFS: Anzahl der Ebenen vom Start.

Trick 7, Zyklus-Erkennung:

• Ungerichtet: DFS, achten auf Kanten zu schon besuchten Knoten (außer Parent).
• Gerichtet: DFS mit drei Farben (weiß/grau/schwarz).

Trick 8, Kanten-Anzahl:

• Ungerichteter Graph mit n Knoten: max. C(n,2) = n(n-1)/2 Kanten.
• Vollständig (alle mit allen) → "K_n".

Trick 9, Eulerweg / Eulerkreis (jede Kante genau einmal, ungerichtet):

• Eulerweg: existiert, wenn genau 0 oder genau 2 Knoten ungeraden Grades haben, und der Graph (ohne isolierte Knoten) zusammenhängend ist.
• Eulerkreis: braucht genau 0 Knoten ungeraden Grades, und der Graph (ohne isolierte Knoten) zusammenhängend ist.

Trick 10, Hamiltonkreis: jeden Knoten genau einmal, NP-schwer, in der Klausur Vorsicht: kein Polynom-Algorithmus bekannt.

Trick 11, Dijkstra-Voraussetzung: Dijkstra nur bei nicht-negativen Kantengewichten. Bei negativen Kanten Bellman-Ford verwenden (oder bei negativen Zyklen die Unmöglichkeit feststellen). Wird in MC-Klausuren gerne als Fallstrick eingebaut.

Wo brauchst du Graphen?

• Maps & Routenplanung: Dijkstra, A*-Algorithmus
• Soziale Netzwerke: Freundschafts-Graph, "Freunde von Freunden" via BFS
• Web-Crawler: Web ist ein gerichteter Graph, Crawler benutzt BFS oder DFS
• Compiler: Abhängigkeits-Graph zwischen Modulen, topologische Sortierung
• AI / Pathfinding: Routensuche per Dijkstra / A*. Spiele-KI nutzt zusätzlich Spielbäume (Game Trees), eine spezielle Baumstruktur, kein allgemeiner Graph.
• Datenbank-Joins: Query-Pläne sind Graphen
• VLSI-Design / Circuit-Layout: physische Layouts modelliert als Graphen
• Bioinformatik: Protein-Interaktions-Netzwerke
• Empfehlungssysteme: User-Item-Bipartite-Graph

Faustregel: wenn die Aufgabe "Verbindungen", "Wege", "Erreichbarkeit", "Reihenfolge mit Abhängigkeiten" beinhaltet, wahrscheinlich Graph.

Graph-Traversal-Spielwiese

Klick einen Knoten als Start, wähle BFS oder DFS, dann Play. Beobachte:

• Aktueller Knoten in Vermillion (gerade besucht)
• Bereits besucht in heller Tönung mit accent-Border
• Frontier (Queue/Stack-Inhalt) als Boxen unten links
• Reihenfolge der Besuche unten rechts (1., 2., 3., …)

Probier folgendes:

• Start A, BFS → ebenenweise: A, B, D, C, E, F, G
• Start A, DFS → in die Tiefe: A, B, C, F, E, D, G (Reihenfolge anders!)
• Start G, BFS → wie viele Schritte bis A erreicht ist? (Antwort: 4)
• Step-Button: einen Schritt manuell machen, statt Auto-Play
• Speed-Toggle 1×/2×/5× für die Animation

Sieh dir den Unterschied zwischen Queue (BFS, FIFO) und Stack (DFS, LIFO) live an, das ist der Kern der beiden Algorithmen.

Faustregel zum Mitnehmen: BFS = ebenenweise (Queue, kürzester Pfad). DFS = in die Tiefe (Stack/Rekursion, Zyklen). Beide laufen in O(V + E), der Unterschied ist die Datenstruktur.

---

Code-Stepper: BFS mit Queue und visited-Set

BFS in Reinform: eine Queue für die Reihenfolge, ein visited-Set gegen Doppelbesuche. Wir starten auf einem kleinen 6-Knoten-Baum (A oben, B/C zweite Ebene, D/E/F dritte Ebene) und schauen wie sich Queue und visited Schritt für Schritt füllen. Klausur-Klassiker: was kommt zuerst aus der Queue?