Ein Graph ist eine Datenstruktur aus Knoten (auch Vertices genannt) und Kanten, die diese verbinden. Graphen modellieren jede Art von Netzwerk: Straßenkarten, soziale Netzwerke, Computernetze oder Abhängigkeiten zwischen Software-Modulen. Eine Baum-Datenstruktur ist ein Sonderfall des Graphen — ein kreisfreier Graph mit genau einer Wurzel.
Gerichtet, ungerichtet, gewichtet
- Ungerichteter Graph: Die Kanten haben keine Richtung — eine Freundschaft in einem sozialen Netzwerk ist beidseitig.
- Gerichteter Graph: Jede Kante hat einen Anfang und ein Ende, etwa bei Einbahnstraßen oder Datenflüssen. Ein gerichteter Graph ohne Zyklen heißt DAG (Directed Acyclic Graph) und kommt bei Build-Systemen oder Abhängigkeiten zum Einsatz.
- Gewichteter Graph: Kanten tragen Zahlen wie Entfernungen oder Kosten — die Grundlage für Routenplanung und kürzeste-Wege-Algorithmen wie Dijkstra.
Speichern von Graphen
Zwei Darstellungen sind üblich: die Adjazenzliste (jeder Knoten führt eine Liste seiner Nachbarn, oft als verkettete Liste oder Array) und die Adjazenzmatrix (eine Tabelle, die für jedes Knotenpaar die Kante angibt). Bei vielen Knoten und wenigen Kanten ist die Adjazenzliste speichereffizienter; dicht besetzte Graphen profitieren von der Matrix.
Durchlaufen: Breitensuche und Tiefensuche
Die Breitensuche (BFS) erkundet einen Graphen Ebene für Ebene und nutzt dafür eine Queue — sie findet den kürzesten Weg in ungewichteten Graphen. Die Tiefensuche (DFS) folgt einem Pfad möglichst weit und kehrt dann zurück; sie arbeitet mit einem Stack oder Rekursion. Beide Verfahren sind fundamentale Algorithmen der Informatik und laufen in O(V+E) mit V Knoten und E Kanten.
Bei der Implementierung spielen Pointer oder Verweise eine zentrale Rolle, Iteratoren erleichtern das Durchlaufen. Zusammen mit der Hash-Tabelle für schnelle Nachbarschaftszugriffe und passenden Datentypen sind Graphen aus der Praxis nicht wegzudenken.