Implementation von Graphen

Es sei jedem Knoten eindeutig ein Index zugeordnet. Für den gerichteten Graphen auf Seite ergibt sich:

Index Knoten

0 a

1 b

2 c

3 d

Implementation durch Adjazenzmatrix

Platzbedarf = O(|V|²) .
Direkter Zugriff auf Kante (i,j) in konstanter Zeit möglich.
Kein effizientes Verarbeiten der Nachbarn eines Knotens.
Sinnvoll bei dicht besetzten Graphen.
Sinnvoll bei Algorithmen, die wahlfreien Zugriff auf eine Kante benötigen.

Implementation durch Adjazenzlisten

Platzbedarf = O(|E|)
Kein effizienter Zugriff auf Kante (x,y) möglich.
Sinnvoll bei dünn besetzten Graphen.
Sinnvoll bei Algorithmen, die, gegeben ein Knoten x , dessen Nachbarn verarbeiten müssen.