当使用二维矩阵来表示元素集合中n个元素的潜在关系时，需要注意一些事项。首先，矩阵需要n2个元素的存储空间，即使有时候元素之间的关系集合非常小。在这些情况下，也就是所谓的稀疏图，由于计算机内存的限制，不可能存储超过数千个顶点的图。例如，Java虚拟机堆使用默认值256MB，创建一个二维的int[4096][4096]矩阵就已经超出可用内存。即使程序员能够在一台有着更多内存的计算机上执行程序，事实上创建的矩阵规模存在一个固定的上界。另外，在大规模矩阵中存储稀疏图，遍历矩阵来寻找边的操作的开销会很大，并且这种存储方法也限制了更多的改进。第二，当顶点之间有多种关系时，不适合使用矩阵。为了能够在矩阵中存储这种关系，矩阵中每一个元素将会当作一个表。
每一种邻接表示法都存储了相同的信息。假设，你写了一个程序，需要计算出世界上任意两个城市之间的最便宜航班。每条边的权重和两个城市之间最便宜直航的价格有关（假设航线不会中转）。根据2005年国际机场协会（ACI）发布的一份报告，世界上有总共1659个机场，这样也就需要一个有2 752 281个条目的二维矩阵。那么就有一个问题：“多少条目是有值的”，它的答案取决于直航航线的数目，ACI的报告也显示，2005年有71 600 000次“航空活动”，简单地说每天有大概196 164次航班。即使所有的航班都是在两个不同机场之间的直航（显然直航的数目要比这个小很多），这个矩阵也有93%是空值——一个非常好的稀疏矩阵的例子！
当使用一个邻接表表示无向图时，我们可以使用一些方法来减少需要的存储空间。假设一个顶点u的邻接顶点为：2、8、1、5、3、10、11和4。首先，这些邻接顶点会以升序来存储，这样做能够快速地定位是否存在一条边（u,v）。在这种结构下，虽然有8个邻接顶点，但是确定是否边（u,6）是否存在只需要6次比较。当然，添加一条边就不再是常数时间，这里我们需要权衡一下利弊。其次，为了能够更加高效地检查是否边（u,v）存在，邻接表可以存储邻接顶点的范围，例子中的邻接表中八个顶点可以减少到三个：1～5、8、10～11。这种方法也能够减少是否存在一条边的计算次数，不过这会降低添加或者删除边的效率。