Dies ist eine alte Version des Dokuments!
Effizienzanalyse
Die verschiedenen Repräsentationen der Graphen haben Vor- und Nachteile. Man kann z.B. den benötigten Speicherplatz und die Laufzeit für Zugriffsoperationen auf den Graphen bewerten.
Dabei muss man Anwendungen unterscheiden, bei denen relativ dünne Graphen auftreten, und Anwendungen, bei denen der Graph (nahezu) vollständig ist.
Repräsentiert der Graph z.B. eine Karte mit Straßen und Kreuzungen, gehen von jedem Knoten (=Kreuzung) nur wenige Kanten (=Straßen) ab. Mehr als 4-5 Straßen gehen üblicherweise nicht von einer Kreuzung aus. Diese Zahl ändert sich auch nicht, wenn die Anzahl der Knoten steigt. Der Graph ist also sehr dünn. Betrachtet man hingegen das Traveling Salesman Problem, dann kann man von jeder Stadt in jede andere reisen. Der Graph ist also vollständig. Bei einer Erhöhung der der Knotenzahl steigt damit auch die Zahl der Kanten pro Knoten.
Speicherplatz (ungerichteter, gewichteter Graph)
- Adjazenzliste: Zwei Zahlen (Nummer des Nachbarknoten, Entfernung) werden gespeichert.
- Adjazenzmatrix: Eine Zahl (Entfernung) wird in jeder Zelle gespeichert (0 für keine Kante).