Multigraph的最佳实现是什么？

Question

在空间和运营成本中，这是实现比顶点更多边的多图的最佳方式吗？

在最坏的情况下，它会有5000条边和1000个顶点。我在考虑一个邻接表，因为它对于add edges，check adjacency between edges,add vertices（几乎所有的时间）等等的大部分操作都有很好的时间......但是它仍然占用了空间|v^2|。

我在正确的轨道上吗？有更好的实施吗？有关实现邻接列表的最佳方式的任何提示？

Answer 1

比率E/V = 5意味着真的非常稀疏的图表，这是一个列表的优点。一般而言，邻接表总体上优于邻接表。

现在的插入成本是O(degree(vertex))，但边缘很少，可以忽略不计。 不要看得更远，请使用邻接列表。