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

Question

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

假设我们将后者表示为

Map<Integer, LinkedList<Integer>> graph;

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

为什么用LinkedList来表示边?难道int[]或ArrayList不能很好地工作吗，或者你想以一种保持顺序的方式来表示边，比如

2 -> 4 -> 1 -> 5

Answer 1

int[]或ArrayList也可以工作。

我不建议马上使用int[]，因为你需要调整大小，以防你从一开始就不知道所有的大小，基本上模拟ArrayList功能，但如果内存是一个问题，它可能是有意义的。

一个LinkedList可能是稍微可取的，因为你需要使数组/ArrayList足够大，以处理可能的最大数量的边，或调整它的大小，在哪里，你没有这个问题与LinkedList，但话又说回来，创建图形可能不是大多数应用程序最资源密集的任务。

底线——对于大多数应用程序来说，它很可能会产生微不足道的差异——只要选择一个您觉得最舒服的(当然，除非您需要大量执行按索引访问，或者其中一个比另一个执行得好得多)。

Answer 2

算法第4版由Sedgewick和Wayne提出了以下对大多数图形处理应用程序有用的图形实现所需的性能特征:

1. 与V + E成比例的空间使用
2. 添加边缘的常数时间
3. 迭代v相邻顶点的时间与v的度数成正比(处理每个相邻顶点的时间为常数)

使用链表来表示每个顶点附近的顶点具有所有这些特征。使用数组而不是链表将导致(1)或(2)无法实现。