prev up next

Previous: Graphen Up: Graphen Next: Graphalgorithmen

Implementation von Graphen

Es sei jedem Knoten eindeutig ein Index zugeordnet. Für den gerichteten Graphen auf Seite gif 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.


prev up next
Previous: Graphen Up: Graphen Next: Graphalgorithmen