Ich weiß, dass es zwei Möglichkeiten gibt, mein Diagramm darzustellen: Eine verwendet eine Matrix und die andere eine Liste.

Wenn ich eine Matrix verwende, muss ich alle Bits in der Matrix spiegeln. Braucht das nicht O (V ^ 2) Zeit?

Wenn ich eine Liste verwende, muss ich dann nicht jede Liste einzeln durchlaufen und eine neue Menge erstellen? Dies scheint eine O (V + E) -Zeit in Anspruch zu nehmen, die linear ist. Hab ich recht?

Also habe ich hier eine andere Frage. Angenommen, ich verwende den Dijkstra-Algorithmus in meinem Diagramm (entweder eine Matrix oder eine Liste) und wir verwenden eine Prioritätswarteschlange für die Datenstruktur hinter den Kulissen. Gibt es eine Beziehung zwischen der Graphendarstellung und der Verwendung der Datenstruktur? Beeinträchtigt dies die Leistung des Algorithmus?

Angenommen, ich würde eine Liste für Darstellungen und eine Prioritätswarteschlange für den Dijkstra-Algorithmus verwenden. Gibt es einen Unterschied zwischen Matrix und Prioritätswarteschlange für Dijkstra?

Ich denke, es bezieht sich aufmakeQueue Betrieb nur? Oder haben sie gar nicht anders?