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:


Ungerichteter Graph für Adjazenzliste

Ungerichteter Graph für Adjazenzliste

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:


Gerichteter Graph für Adjazenzliste

Gerichteter Graph für Adjazenzliste

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.