Multigraph的最佳實現是什麼？

Question

在空間和運營成本中，這是實現比頂點更多邊的多圖的最佳方式嗎？

在最壞的情況下，它會有5000條邊和1000個頂點。我在考慮一個鄰接表，因爲它對於add edges，check adjacency between edges,add vertices（幾乎所有的時間）等等的大部分操作都有很好的時間......但是它仍然佔用了空間|v^2|。

我在正確的軌道上嗎？有更好的實施嗎？有關實現鄰接列表的最佳方式的任何提示？

Answer 1

比率E/V = 5意味着真的非常稀疏的圖表，這是一個列表的優點。一般而言，鄰接表總體上優於鄰接表。

現在的插入成本是O(degree(vertex))，但邊緣很少，可以忽略不計。 不要看得更遠，請使用鄰接列表。