什么类型的应用程序是每个数据结构用于存储图形的边缘最适合？

Question

这是来自我正在进行的练习测试...不知道如何回答这个问题：

考虑在图中存储边（邻接矩阵，邻接列表，边列表）的三种数据结构。每种数据结构最适合哪种类型的应用程序？

纠正我，如果我错了，但据我所知，邻接矩阵是表示图的效率最低的方法，因为二维数组中的元素表示不存在的边，而其他两个数据结构只包含表示存在边缘的元素，因此任何操作的遍历速度都较慢。如果这是真的，那么为什么有人想使用它？

对于邻接列表，它比邻接矩阵更有效，但仍包含冗余信息 - >如果边连接顶点i和j，则包含顶点i的顶点节点出现在顶点的邻接列表中j并且同时包含顶点j的顶点节点出现在顶点i的邻接列表中。

而...边缘列表是最有效的。

因此，重申我的问题....如果一个边界列表是最有效的表示，为什么你会想要使用其他两个之一呢？

任何帮助，将不胜感激，谢谢。

Answer 1

你只是在谈论空间效率问题。还有时间。如果您有顶点数字，矩阵只需要一条或几条指令来查找边缘值。你不能变得更快。实现和维护也非常简单。 （不利的一面是，它需要O（n^2）来初始化，而不管边数是多少，但是有一个解决方案。）其他形式都涉及某种搜索。即使您将邻接列表作为O（1）访问的哈希值，时间常数因子远远高于矩阵。边缘列表只有在处理边缘时才有意义，不需要根据顶点查找边缘。