Die Adjazenzliste ist eine Möglichkeit, einen Graphen im Speicher abzubilden: Für jeden Knoten wird eine Liste seiner direkten Nachbarn geführt (adjacent = benachbart). Zusammen mit der Adjazenzmatrix ist sie die klassischste Graph-Repräsentation in der Informatik.
Idee
Ein ungerichteter Graph mit vier Knoten A, B, C und D lässt sich als Wörterbuch schreiben, das jedem Knoten seine Nachbarn zuordnet:
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"],
}Gewichtete Kanten werden ergänzt, indem die Liste Tupel aus Nachbar und Gewicht führt: "A": [("B", 5), ("C", 2)]. So arbeitet auch der Dijkstra-Algorithmus typischerweise.
Eigenschaften
- Platzbedarf: O(V + E) — nur Nachbarn, die wirklich existieren, belegen Speicher (V = Knoten, E = Kanten).
- Nachbarn auflisten: sehr schnell, direkt beim Knoten verfügbar — ideal für die Traversierung eines Graphen.
- Kantenabfrage: „Existiert eine Kante von A nach B?“ kostet im Durchschnitt O(Grad von A) — bei wenigen Nachbarn praktisch konstant.
Implementiert wird die Adjazenzliste meist mit Arrays oder verketteten Listen pro Knoten.
Wann Adjazenzliste, wann Adjazenzmatrix?
Die Adjazenzliste gewinnt bei dünnen Graphen (wenige Kanten im Verhältnis zu den Knoten): Sie spart Speicher und erlaubt schnelles Durchlaufen aller Nachbarn. Die Adjazenzmatrix ist dagegen bei dichten Graphen und häufigen Kantenabfragen im Vorteil. Viele Algorithmen lassen sich mit beiden Darstellungen formulieren — die Wahl beeinflusst Laufzeit und Speicherverbrauch.