マルチグラフに最適な実装は何ですか？

Question

頂点よりもエッジの多いマルチグラフを実装する最良の方法は、スペースと操作コストの両方でですか？

最悪の場合、エッジが5000個、頂点が1000個です。 add edges、check adjacency between edges、add vertices（ほとんどいつも）などの操作の大部分が素晴らしい時間を持っているので、私は隣接リストを考えていましたが、それでもまだ|v^2|のスペースを消費します。

私は適切なトラックにいますか？より良い実装がありますか？隣接関係リストを実装する最善の方法に関するヒント

Answer 1

比率E/V = 5は実際には非常に疎なグラフを意味し、これはリストにプラスです。一般に、隣接関係リストは隣接関係マトリックスよりも全体的に優れています。

ここで、挿入コストはO(degree(vertex))ですが、エッジがごくわずかなため無視できます。 さらに見ないで、隣接リストを使用してください。