java - 当用邻接矩阵表示稀疏图时，为什么使用链表作为包含边的结构？

Question

当用 Java 等语言表示内存中的图时，要么使用邻接矩阵(对于密集图)，要么使用邻接列表(对于稀疏图)。

所以说我们代表后者，就像

Map<Integer, LinkedList<Integer>> graph;

整数键代表顶点，LinkedList包含它指向的所有其他顶点。

为什么使用 LinkedList 来表示边？ int[] 或 ArrayList 不能同样正常工作，或者是否有理由希望以保持顺序的方式表示边缘，例如

2 -> 4 -> 1 -> 5

Answer 1

int[] 或 ArrayList 也可以工作。

不过，我不会立即推荐 int[] ，因为如果您从一开始就不知道所有尺寸，则需要调整大小，本质上是模拟ArrayList 功能，但如果内存有问题，它可能有意义。

LinkedList 可能稍微好一些，因为您需要使数组/ArrayList 足够大以处理最大数量的可能边，或者将其大小调整为你去吧，因为 LinkedList 不会出现这个问题，但话又说回来，对于大多数应用程序来说，创建图表可能不是最消耗资源的任务。

底线 - 对于大多数应用程序来说，它的影响很可能可以忽略不计 - 只需选择您觉得最舒服的一个即可(当然，除非您需要经常按索引访问，或者需要执行以下其中一项操作)两个的表现比另一个好得多)。