Was sind Graphen und wie durchsuchen wir sie?
Das Konzept: Netzwerke aus Knoten und Kanten
Du kennst bereits Bäume als hierarchische Datenstrukturen. Ein Graph ist die Verallgemeinerung eines Baumes: ein flexibles Netzwerk ohne zwingenden Startpunkt (Wurzel), das komplexe Beziehungen modelliert. Graphen bestehen aus zwei fundamentalen Bausteinen:
- Knoten (Vertices): Die eigentlichen Objekte oder Entitäten. Das können Städte auf einer Landkarte, Personen in einem sozialen Netzwerk oder Router im Internet sein.
- Kanten (Edges): Die Verbindungen zwischen diesen Objekten. Das sind beispielsweise die Straßen zwischen den Städten, die Freundschaften zwischen Personen oder die Glasfaserkabel zwischen Routern.
Kantenarten: Richtung und Gewichtung
Wie in der zugehörigen Grafik visualisiert, lassen sich Kanten nach zwei Hauptkriterien klassifizieren, um die Realität exakt abzubilden:
- Richtung: In einem ungerichteten Graphen gelten Verbindungen immer beidseitig (z. B. eine normale Straße oder eine Freundschaft – wenn Person A mit Person B befreundet ist, gilt das auch umgekehrt). In einem gerichteten Graphen (Digraph) besitzen die Kanten Pfeile und geben eine klare Richtung vor (z. B. Einbahnstraßen oder Follower auf Social Media).
- Gewichtung: In einem ungewichteten Graphen zählt nur die reine Existenz der Verbindung. In einem gewichteten Graphen erhält jede Kante einen spezifischen Wert (das Gewicht). Dieser Wert repräsentiert beispielsweise die Distanz in Kilometern zwischen zwei Städten oder die Übertragungsdauer in einem Computernetzwerk.
Breitensuche (Breadth-First Search): Schicht für Schicht
Um Informationen in einem Graphen zu finden, nutzen wir Traversierungsalgorithmen. Die Breitensuche (BFS) erkundet den Graphen schichtweise: Sie prüft erst alle direkten Nachbarn eines Startknotens, bevor sie zu den Nachbarn der Nachbarn übergeht.
Da du die Datenstruktur Queue (Warteschlange) bereits kennst, weißt du, wie die BFS im Hintergrund implementiert wird: Sie nutzt das FIFO-Prinzip (First-In-First-Out), um die zu besuchenden Knoten zwischenzuspeichern.
- Anwendungsfall: Die BFS ist ideal, um in einem ungewichteten Graphen den kürzesten Pfad zu finden (z. B. "Über wie viele Ecken bin ich mit Person X im sozialen Netzwerk verbunden?").
Tiefensuche (Depth-First Search): Bis in die Sackgasse
Die Tiefensuche (DFS) verfolgt eine völlig andere Strategie: Sie geht von einem Startknoten aus so tief wie möglich in einen Pfad hinein, bis es nicht mehr weitergeht (Sackgasse). Erst dann springt sie zurück (Backtracking) und probiert die nächste Abzweigung.
Für die Implementierung nutzt die DFS einen Stack (Stapelspeicher) nach dem LIFO-Prinzip (Last-In-First-Out), den du ebenfalls schon kennengelernt hast.
- Anwendungsfall: Die DFS eignet sich hervorragend, um Labyrinthe zu lösen, Zyklen in einem Netzwerk zu erkennen oder generell zu prüfen, ob überhaupt ein Weg zwischen zwei bestimmten Knoten existiert.
Wie werden Graphen im Speicher repräsentiert?
Die Adjazenzmatrix: Der tabellarische Ansatz
Eine Adjazenzmatrix ist ein zweidimensionales Array (eine quadratische Tabelle), bei der sowohl die Zeilen als auch die Spalten die Knoten des Graphen repräsentieren. Existiert eine Kante von Knoten A zu Knoten B, wird in der Zelle Matrix[A][B] eine 1 (oder bei gewichteten Graphen das Gewicht) eingetragen. Fehlt die Verbindung, steht dort eine 0.
- Vorteil: Der Zugriff ist extrem schnell (O(1)). Um zu prüfen, ob zwei Knoten verbunden sind, muss das System nur eine einzige Speicherzelle abfragen.
- Nachteil: Der Speicherbedarf wächst quadratisch mit der Anzahl der Knoten (O(V²)). Ein Graph mit 10.000 Knoten belegt 100 Millionen Speicherzellen, selbst wenn es kaum Verbindungen gibt.
Die Adjazenzliste: Der knotenbasierte Ansatz
Da du verkettete Listen bereits kennst, wirst du die Adjazenzliste schnell verstehen. Sie nutzt ein eindimensionales Array, in dem jeder Index für einen Knoten steht. An jedem Index hängt eine verkettete Liste, die ausschließlich die direkten Nachbarn dieses Knotens speichert (wie in der Grafik durch die zeigerverknüpfte Struktur visualisiert).
- Vorteil: Sie ist extrem speichereffizient, da nur tatsächlich existierende Kanten Speicherplatz verbrauchen.
- Nachteil: Um zu prüfen, ob Knoten A mit Knoten B verbunden ist, muss die gesamte verkettete Liste von Knoten A sequenziell durchsucht werden. Die Zugriffsgeschwindigkeit für diese spezifische Abfrage ist also geringer als bei der Matrix.
Praxisvergleich: Wann wählst du welche Repräsentation?
Die Wahl zwischen Matrix und Liste hängt maßgeblich von der Dichte des Graphen ab:
- Dicht besetzte Graphen (Dense Graphs): Wenn fast jeder Knoten mit jedem anderen verbunden ist, lohnt sich die Adjazenzmatrix. Der hohe Speicherbedarf ist gerechtfertigt, da die Tabelle ohnehin fast voll ist, und du profitierst von der maximalen Zugriffsgeschwindigkeit.
- Dünn besetzte Graphen (Sparse Graphs): Ein reales Straßennetzwerk hat Millionen von Kreuzungen (Knoten), aber jede Kreuzung ist meist nur mit drei bis vier anderen verbunden. Hier wäre eine Matrix fast komplett mit Nullen gefüllt – eine massive Speicherverschwendung. Für solche Graphen ist die Adjazenzliste die einzig sinnvolle und performante Wahl.
Teste dein Wissen
Du modellierst das Straßennetz einer Großstadt für ein Navigationssystem. Warum eignet sich hierfür ein Graph besser als ein klassischer Baum?