algorithm - マルチグラフの最適な実装は何ですか?

Question

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

最悪の場合、5000 個のエッジと 1000 個の頂点があります。add edges、check adjacency between edges、 （ほぼ常に）などのほとんどの操作に最適な時間があるため、隣接リストを考えていましたadd verticesが、それでも . のスペースを消費します |v^2|。

私は正しい軌道に乗っていますか？より良い実装はありますか？隣接リストを実装する最良の方法に関するヒントはありますか?

Answer 1

比率E/V = 5は、本当にまばらなグラフを意味します。これは、リストにとってプラスです。一般に、隣接リストは全体的に隣接行列よりも優れています。

現在、挿入のコストは ですO(degree(vertex))が、エッジが非常に少ないため、無視できます。これ以上探さないで、隣接リストを使用してください。