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.

• Adjazenzliste: Zwei Zahlen (Nummer des Nachbarknoten, Entfernung) werden gespeichert.
• Adjazenzmatrix: Eine Zahl (Entfernung) wird in jeder Zelle gespeichert (Die Zahl 0 für keine Kante).

Vervollständige die folgende Tabelle und formulieren einen Ergebnissatz für die Bewertung des Speicherplatzbedarfs.

Die Laufzeit einzelner Operationen hängt von der Art der Implementierung ab.

• Adjazenzliste: Ein Array enthält für jeden Knoten eine einfach verkettete Liste der Kanten.
• Adjazenzmatrix: Zweidimensionales Array.

Vervollständige die folgende Tabelle und formuliere einen Ergebnissatz für die Bewertung des Laufzeitverhaltens bei den gegebenen Implementierungen.