Ein gerichteter Graph (auch Digraph, von englisch directed graph) ist eine Graph-Datenstruktur, bei der jede Kante eine Richtung besitzt: Sie verläuft von einem Knoten zu einem anderen und kann nicht einfach in beide Richtungen benutzt werden. Man zeichnet gerichtete Kanten als Pfeile.
Formale Definition
Ein gerichteter Graph ist ein Paar G = (V, E) aus einer Knotenmenge V und einer Kantenmenge E. Jede Kante ist ein geordnetes Paar (u, v): Sie führt von u nach v. Die Reihenfolge ist entscheidend — (u, v) und (v, u) sind verschiedene Kanten.
Beispiele aus der Praxis
- Straßennetze mit Einbahnstraßen
- Folge-Beziehungen in sozialen Netzwerken (wer folgt wem?)
- Abhängigkeiten zwischen Tasks oder Software-Modulen
- Datenflüsse in Pipelines oder Netzwerken (wer sendet an wen?)
Darstellung und Kenngrößen
Gerichtete Graphen werden wie ungerichtete als Adjazenzliste oder Adjazenzmatrix gespeichert. Bei der Matrix ist die Darstellung im Gegensatz zum ungerichteten Graphen nicht symmetrisch. Statt des einfachen Knotengrads unterscheidet man den Ausgangsgrad (abgehende Kanten) und den Eingangsgrad (ankommende Kanten). Ein Zyklus entsteht, wenn man über gerichtete Kanten zum Ausgangsknoten zurückkehren kann.
Wichtige Spezialfälle und Algorithmen
- Ein gerichteter Graph ohne Zyklen heißt DAG (gerichteter azyklischer Graph) und lässt sich topologisch sortieren.
- Dijkstra findet kürzeste Wege in gerichteten Graphen ohne negative Kantengewichte.
- Bellman-Ford kommt auch mit negativen Kanten zurecht und erkennt negative Zyklen.
Verwandte Grundlagen: Graph-Datenstruktur und Traversierung.