Adjazenzmatrix vs Adjazenzliste für gerichtete gewichtete Grafik

Question

Als Übung muss ich ein Navigationsgerät bauen, das die kürzesten und schnellsten Routen von Ort zu Ort plant. Es muss so schnell wie möglich sein, ohne zu viel Speicher zu verbrauchen.

Ich habe Probleme zu entscheiden, welche Struktur verwendet werden soll, um das Diagramm darzustellen. Ich verstehe, dass eine Matrix für dichte Graphen besser ist und dass eine Liste für dünnere Graphen besser wäre. Ich neige mehr dazu, eine Liste zu verwenden, da ich annahm, dass das Hinzufügen von Scheitelpunkten der beste Teil dieses Programms sein wird.

Ich möchte nur einige der Meinungen Ihrer Jungs bekommen. Wenn ich eine typische Straßenkarte als eine Grafik betrachten würde, bei der verschiedene Orte Knoten und Straßen Kanten sind. Würden Sie es als spärlich oder dicht betrachten? Welche Struktur scheint in diesem Szenario besser zu sein?

Answer 1

Ich würde für Listen gehen, weil es nur 1 Mal Investition. Das gute daran ist, dass es über alle benachbarten Vertices iterieren kann schneller als Matrix, die eine wichtige und häufigste Schritte in den meisten Algorithmen des kürzesten Pfades ist.

Also wo Matrix ist O (N) Adjazenzliste geht nur O (k) wobei k ist die Anzahl der benachbarten Ecken.