Was ist die beste Implementierung für einen Multigraphen?

Question

Was ist sowohl hinsichtlich der Platz- als auch der Betriebskosten der beste Weg, um einen Multigraphen mit mehr Kanten als Eckpunkten zu implementieren?

Im schlimmsten Fall hätte es 5000 Kanten und 1000 Eckpunkte.Ich habe an eine Nachbarschaftsliste gedacht, weil sie für die meisten Operationen eine großartige Zeit hat, wie add edges, check adjacency between edges, add vertices (fast die ganze Zeit) usw....aber es verbraucht immer noch einen Raum von |v^2|.

Bin ich auf dem richtigen Weg?Gibt es eine bessere Umsetzung?Irgendwelche Tipps zur besten Implementierung der Adjazenzliste?

Answer 1

Verhältnis E/V = 5 bedeutet wirklich sehr spärliche Grafiken, was ein Plus für Listen ist.Im Allgemeinen sind Adjazenzlisten insgesamt besser als Adjazenzmatrizen.

Jetzt betragen die Kosten für die Einfügung O(degree(vertex)) aber mit so wenigen Kanten wird es vernachlässigbar sein.Suchen Sie nicht weiter, verwenden Sie Nachbarschaftslisten.