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(\vert V\vert^{2})$.
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(\vert E\vert)$
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.