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²).
