Datenstrukturen für Graphen < Datenstrukturen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:19 So 02.03.2008 | | Autor: | koker |
| Aufgabe | | Es existieren ja 4 Arten: Adjazenzmatrix, Adjazenzliste, Inzidenmatrix und Kantenliste. Ich soll nun berschreiben welche der Methoden die beste ist und welche würde man bevorzugen. |
Ich weiß leider nicht, nach welchen Kriterien soll ich das beurteilen.
Man könnte ja die Adjazenzliste mit der Adjazenzmatrix vergleichen aber wie soll ich die anderen 2 dann noch vergleichen (nach welchen Kriterien)?
mfg Marcin
|
|
| |
|
Hallo,
typischerweise geht es bei solchen Bewertungen um den Speicherbedarf solcher Darstellungen und die Zeit, die für typische Operationen benötigt wird.
Du kannst versuchen, den Speicherbedarf aller Darstellungen in Abhängigkeit zur Knoten- und zur Kantenzahl abzuschätzen.
Entsprechend untersuchst du die typischen Operationen Einfügen/Löschen von Knoten/Kanten auf ihren Aufwand. Außerdem kann nach der Existenz einer Kante zwischen zwei bestimmten Knoten gefragt sein.
Aus der Gegenüberstellung nach diesen (und weiteren?) Kriterien kannst du deinen Favoriten (evtl. anwendungsabhängig) heraussuchen.
Gruß
Martin
|
|
|
|
