Adjazenzliste
Adjazenzliste Definition
Eine Adjazenzliste (adjazent: benachbart zu) enthält bei ungerichteten Graphen für jeden Knoten eines Graphen eine Liste mit allen Nachbarknoten, also der Knoten, mit denen der jeweils betrachtete Knoten verbunden ist.
Bei gerichteten Graphen werden nur die Nachfolger in die Liste aufgenommen.
Beispiel
Beispiel: Adjazenzliste für ungerichteten Graphen
Es gibt einen ungerichteten Graphen mit 3 Knoten A, B und C (das könnten zum Beispiel Städte sein).
A ist mit B und mit C verbunden (etwa durch eine Bahnstrecke). Ungerichtet bedeutet, die Knoten / Städte sind mit Kanten verbunden, nicht mit Pfeilen (das hieße gerichteter Graph). Man kann also von A nach B fahren und von B nach A, während bei einem gerichteten Graphen die Verbindung nur in Pfeilrichtung befahrbar ist (zum Beispiel nur von A nach B, nicht aber von B nach A).
In einem Graphen kann man die Knoten und die Verbindungen einfach sehen. Ein Computer braucht eine andere Darstellung, zum Beispiel die Adjazenzliste:
A: B, C
B: A
C: A
Lesebeispiele:
1. Zeile: A ist mit B und C verbunden.
2. Zeile: B ist mit A verbunden.
3. Zeile: C ist mit A verbunden.
Beispiel: Adjazenzliste für gerichteten Graphen
Ändern wir das Beispiel so ab, dass von A ein Pfeil nach B geht und von C ein Pfeil nach A.
Dann ist die Adjazenzliste:
A: B
B: (leer)
C: A
Lesebeispiele:
1. Zeile: Von A führt ein Pfeil nach B.
2. Zeile: Von B führt kein Pfeil.
3. Zeile: Von C führt ein Pfeil nach A.