TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Ausarbeitung Tests/20080131 2.A.b

analyse                          matrix           liste               
-------------------------------  ---------------  --------------------
abfrage: existiert kante (v,w)?  $\Theta(1)$      $\Theta(Valency(v))$
iteration ueber nachbarn von v   $\Theta(|V|)$    $\Theta(Valency(v))$
speicherverbrauch                $\Theta(|V|^2)$  $\Theta(|E|+|V|)$ 

ist der graph dünn, ist eine adjazenzliste besser geeignet, da der knotengrad (engl. Valency) kleiner ist als die anzahl aller knoten im graphen.