algorithm - 多图的最佳实现是什么？

Question

在空间和操作成本方面，哪一种是实现边多于顶点的多重图的最佳方式？

在最坏的情况下，它将有 5000 个边和 1000 个顶点。我正在考虑一个邻接列表，因为它对于大多数操作（例如add edges, check adjacency between edges, add vertices（几乎所有时间）等）都有很好的时间......但它仍然消耗 |v^2|.

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

Answer 1

比率E/V = 5意味着非常稀疏的图，这对于列表来说是一个加分项。一般来说，邻接列表总体上优于邻接矩阵。

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