Graphenalgorithmen — Kürzeste Wege und Netzwerke

Einführung

Wie berechnet Google Maps den schnellsten Weg von Berlin nach München? Wie findet ein E-Mail-System heraus, über welche Server eine Nachricht geleitet werden soll? Wie empfiehlt dir LinkedIn neue Kontakte über gemeinsame Bekannte?

All diese Fragen lassen sich als Graphprobleme modellieren. Graphen sind eine der mächtigsten und vielseitigsten Datenstrukturen der Informatik. Sie beschreiben Verbindungen — zwischen Orten, Personen, Webseiten, Computern.

Und die Algorithmen, die auf Graphen operieren, sind das Rückgrat moderner Infrastruktur: Navigation, Social Networks, Internet-Routing, Logistik, Empfehlungssysteme.

Grundidee

Ein Graph besteht aus:

• Knoten (Vertices): Die Objekte — Städte, Personen, Webseiten.
• Kanten (Edges): Die Verbindungen zwischen je zwei Knoten.

Ein Graph ist allgemeiner als ein Baum: Graphen können Zyklen haben (du kannst im Kreis gehen), mehrere verbundene Komponenten haben, oder gerichtet sein (Kante geht nur in eine Richtung).

Erklärung

Arten von Graphen

• Ungerichtet: Kante zwischen A und B gilt in beide Richtungen. Beispiel: Freundschaft auf Facebook.
• Gerichtet: Kante von A nach B gilt nur in eine Richtung. Beispiel: Folgen auf Instagram.
• Gewichtet: Jede Kante hat ein Gewicht (z. B. Distanz, Kosten). Beispiel: Straßen mit Kilometerzahl.
• Ungewichtet: Alle Kanten sind gleichwertig.

Darstellung im Speicher

Adjazenzliste: Für jeden Knoten eine Liste seiner Nachbarn.

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

Speichereffizient für dünn besetzte Graphen (wenige Kanten).

Adjazenzmatrix: Ein n×n-Raster, Eintrag [i][j] = 1, wenn Kante i→j existiert. Schneller für Kantenabfragen, aber O(n²) Speicher.

Breitensuche (BFS — Breadth-First Search)

Idee: Erkunde alle Nachbarn eines Knotens, bevor du zu deren Nachbarn gehst. Benutze eine Warteschlange.

Algorithmus:

1. Starte beim Startknoten, markiere ihn als besucht, lege ihn in die Queue.
2. Nimm einen Knoten aus der Queue.
3. Füge alle unbesuchten Nachbarn in die Queue, markiere sie.
4. Wiederhole, bis Queue leer.

Eigenschaft: BFS findet bei ungewichteten Graphen den kürzesten Weg (gemessen in Kanten-Anzahl).

Laufzeit: O(V + E), wobei V die Anzahl der Knoten (Vertices) und E die Anzahl der Kanten (Edges) ist.

Anwendung: Kürzester Weg in ungewichteten Graphen, Kontakt-Grad bei Social Networks (Freunde in zweitem Grad), Web-Crawler.

Tiefensuche (DFS — Depth-First Search)

Idee: Gehe so tief wie möglich in eine Richtung, bevor du zurückgehst. Benutze einen Stapel (oder Rekursion).

Algorithmus (rekursiv):

DFS(knoten):
  markiere knoten als besucht
  für jeden Nachbarn von knoten:
    wenn nicht besucht: DFS(Nachbar)

Eigenschaft: DFS findet nicht zwingend den kürzesten Weg, aber es ist einfacher zu implementieren und gut zum Erkunden aller Knoten.

Anwendung: Zusammenhangsprüfung, Zykluserkennung, topologische Sortierung, Labyrinth-Lösung.

Dijkstra-Algorithmus: Kürzester Weg in gewichteten Graphen

BFS funktioniert für ungewichtete Graphen. Bei gewichteten Graphen (z. B. Straßen mit unterschiedlichen Längen) braucht man Dijkstra.

Idee: Halte für jeden Knoten die bisher bekannte günstigste Gesamtdistanz vom Start. Bearbeite immer zuerst den Knoten mit der kleinsten bekannten Distanz, und versuche, über ihn die Distanzen zu seinen Nachbarn zu verbessern.

Schritt-für-Schritt-Beispiel:

Graph: A → B (4), A → C (2), C → B (1), B → D (5), C → D (8)

Startknoten: A

Schritt	Bearbeitet	dist(A)	dist(B)	dist(C)	dist(D)
Start	—	0	∞	∞	∞
1	A	0	4	2	∞
2	C (dist=2)	0	3 (via C)	2	10
3	B (dist=3)	0	3	2	8
4	D (dist=8)	0	3	2	8

Kürzester Weg von A nach D: A → C → B → D (Länge 8).

Laufzeit: O((V + E) log V) mit einer Priority Queue (Heap).

Wichtig: Dijkstra funktioniert nicht mit negativen Kantengewichten (dann: Bellman-Ford).

Minimaler Spannbaum (MST) und Kruskal

Ein Spannbaum eines Graphen ist ein Teilgraph, der alle Knoten verbindet und dabei keine Zyklen enthält (also ein Baum). Ein minimaler Spannbaum hat unter allen möglichen Spannbäumen das geringste Gesamtkantengewicht.

Warum relevant? Wenn du ein Netzwerk (z. B. Internet-Kabel zwischen Städten) aufbauen willst, das alle Punkte verbindet und dabei möglichst günstig ist — das ist ein MST-Problem.

Kruskal-Algorithmus:

1. Sortiere alle Kanten nach Gewicht (aufsteigend).
2. Füge jede Kante hinzu, wenn sie keinen Zyklus erzeugt.
3. Stoppe, wenn n-1 Kanten vorhanden sind (bei n Knoten genug für einen Baum).

Die Zyklusprüfung funktioniert effizient mit einer Datenstruktur namens Union-Find.

Laufzeit: O(E log E) für das Sortieren.

Beispiel aus dem Alltag

Navigation (Dijkstra):

Google Maps berechnet den schnellsten Weg als Dijkstra-Variante auf einem gewichteten, gerichteten Graphen. Knoten sind Kreuzungen, Kanten sind Straßen, Gewichte sind Fahrzeiten (dynamisch angepasst durch Echtzeit-Verkehrsdaten). Dijkstra findet den Weg mit der kürzesten Gesamtfahrzeit.

Social Networks (BFS):

LinkedIn berechnet „Verbindungen 2. Grades”: Wer kennt jemanden, der dich kennt? Das ist BFS vom eigenen Knoten mit Tiefe 2. Der Algorithmus erkundet alle direkte Verbindungen (Tiefe 1), dann alle deren Verbindungen (Tiefe 2).

Paketrouting im Internet:

Das Internet ist ein riesiger Graph aus Routern (Knoten) und Verbindungen (Kanten). Routing-Protokolle wie OSPF (Open Shortest Path First) basieren auf Dijkstra-ähnlichen Algorithmen, um Datenpakete auf dem schnellsten Weg vom Absender zum Empfänger zu leiten.

Stromnetz-Planung (MST):

Ein Energieunternehmen will alle Städte einer Region mit Strom versorgen und dabei möglichst wenig Kabel verlegen. Das ist ein MST-Problem: Verbinde alle Städte mit möglichst kurzen Leitungen ohne redundante Verbindungen.

Anwendung

Betrachte diesen Graphen (Gewichte in Minuten Fahrzeit):

• A → B: 5
• A → C: 8
• B → D: 3
• C → D: 2
• C → E: 7
• D → E: 4

Startknoten: A

1. Führe Dijkstra manuell durch: Was ist der kürzeste Weg von A nach E?
2. Führe BFS durch (ungewichtet): Was ist der Weg mit den wenigsten Kanten von A nach E?
3. Sind die beiden Wege identisch? Was sagt das über den Unterschied zwischen BFS und Dijkstra?

Typische Fehler

Graphen und Bäume verwechseln: Bäume sind eine spezielle Art von Graphen (zusammenhängend, azyklisch, mit Wurzel). Nicht jeder Graph ist ein Baum — Graphen können Zyklen haben und müssen nicht zusammenhängend sein.

BFS für gewichtete Graphen verwenden: BFS findet den Weg mit den wenigsten Kanten, nicht den mit dem kleinsten Gesamtgewicht. Bei unterschiedlichen Kantengewichten braucht man Dijkstra.

Dijkstra mit negativen Gewichten: Dijkstra setzt voraus, dass Kantengewichte nicht negativ sind. Sonst kann der bereits „fertig bearbeitete” Knoten später noch verbessert werden — das bricht den Algorithmus. Für negative Kanten: Bellman-Ford.

DFS für kürzesten Weg: DFS findet irgendeinen Weg, aber nicht zwingend den kürzesten.

Zusammenfassung

• Graphen bestehen aus Knoten und Kanten; sie können gerichtet, ungerichtet, gewichtet oder ungewichtet sein
• BFS (Breitensuche): findet kürzesten Weg in ungewichteten Graphen; nutzt eine Queue; O(V + E)
• DFS (Tiefensuche): erkundet so tief wie möglich; nutzt Stapel oder Rekursion; gut für Erreichbarkeit und Zykluserkennung
• Dijkstra: findet kürzeste Wege in gewichteten Graphen mit nicht-negativen Gewichten; O((V + E) log V)
• Minimaler Spannbaum: verbindet alle Knoten mit minimalem Gesamtgewicht; Kruskal sortiert Kanten und fügt zyklusfrei ein
• Anwendungen: Navigation (Dijkstra), Social Networks (BFS), Internet-Routing, Netzwerk-Planung (MST)

Quiz

Frage 1: Was ist der Unterschied zwischen BFS und DFS — und wann ist jede Methode besser geeignet?

Frage 2: Erkläre das Grundprinzip von Dijkstra in eigenen Worten.

Frage 3: Was ist ein minimaler Spannbaum — und wofür wird er in der Praxis verwendet?

Frage 4: Warum funktioniert Dijkstra nicht bei negativen Kantengewichten?