1.4 图的表示方法
我们可以采用不止一种方法对图进行编码，以便在算法中使用。
在本系列图书中，我们主要采用图的“邻接列表”表示形式（见1.4.1节），但读者同时也应该熟悉“邻接矩阵”表示形式（见1.4.2节）。
1.4.1 邻接列表
图的邻接列表表示形式是我们在本系列图书中采用的主要形式。
邻接列表的组成部分
1．一个包含图的顶点集的数组。
2．一个包含图的边集的数组。
3．对于每条边，有一个指针指向它的每个顶点。
4．对于每个顶点，有一个指针指向它的每条关联边。
邻接列表表示形式可以简化为两个数组（或者链表）：一个用于记录顶点，另一个用于记录边。这两个数组以一种自然的方式交叉引用对方，每条边都有相关联的指针指向它的每个顶点，每个顶点都有指针指向以它为顶点的边。
对于有向图，每条边记录哪个顶点是尾顶点，哪个顶点是头顶点。每个顶点v维护两个指针数组，一个表示外向边（v是尾顶点），另一个表示入射边（v是头顶点）。
邻接列表表示形式的内存需求是怎么样的呢？
小测验1.2
图的邻接列表表示形式需要多大的空间？（用顶点数量和边的数量的函数形式表示。）
（a）Θ (n)
（b）Θ (m)
（c）Θ (m+n)
（d）Θ (n2)
（正确答案和详细解释参见1.4.4节。）
1.4.2 邻接矩阵
考虑一个无向图G=(V, E)，它具有n个顶点且没有平行边，并用1,2,3,…,n标识它的顶点。G的邻接矩阵表示形式是一个正方形的n×n矩阵A，相当于一个二维数组，其元素是0或1。每个元素Aij被定义为：
如果边(i, j)属于E，则Aij=1；
否则，Aij=0。
因此，邻接矩阵用一个位表示每一对顶点，标记这对顶点之间是否存在边（见图1.7）。
图1.7 图的邻接矩阵为每一对顶点维护一个位，
表示是否存在一条边连接这两个顶点
我们可以很方便地在图的邻接矩阵表示形式中添加一些“花样”，提示更多的信息。
•平行边。如果在同一对顶点之间有多条边，那么Aij可以定义为顶点i和j之间的边数。
•权重图。类似地，如果每条边(i, j)具有权重wij，例如表示价格或距离，那么每个元素Aij可以存储wij。
•有向图。对于有向图G，邻接矩阵的每个元素被定义为：
如果边(i, j)属于E，那么Aij=1；
否则，Aij=0。
现在，“边(i, j)”表示从i到j的有向边。每个无向图的邻接矩阵都是对称的，但有向图的邻接矩阵通常是不对称的。
邻接矩阵的内存需求是怎么样的呢？
小测验1.3
图的邻接矩阵需要占据多大的内存空间呢？（用顶点数量n和边的数量m的函数形式表示。）
（a）Θ (n)
（b）Θ (m)
（c）Θ (m+n)
（d）Θ (n2)
（正确答案和详细解释参见1.4.4节。）
1.4.3 图的表示形式之间的比较
图有两种不同的表示形式也是一件令人烦恼的事情。我们不禁会问：哪种形式更好呢？答案通常是“取决于具体情况”。首先，它取决于图的密度，也就是边的数量与顶点的数量的相对数量比。小测验1.2和小测验1.3向我们提示邻接矩阵用于表示稠密图是非常高效的，但用来表示稀疏图是极为浪费的。其次，它取决于我们要支持的操作。综合考虑之下，对于本系列图书所描述的算法和应用，邻接列表是更为合理的表示形式。
大多数与图有关的算法涉及图的探索。邻接列表非常适合进行图的探索，当我们访问一个顶点时，邻接列表立即就能告诉我们接下来可以在哪几个步骤中进行选择。
邻接矩阵也有一些合适的应用，但本系列图书并不会讨论这些应用。
当前对快速图元的兴趣大多来自于巨大的稀疏网络。例如，我们可以考虑Web图（见1.2节），其中顶点对应于Web页面，有向边对应于超链接。对这种类型的图的大小进行精确的测量是非常困难的，但还是在现代计算机的能力范围之内。保守地估计，顶点数量的下界大约是100亿（1010）。存储和读取如此长度的数组需要巨量的计算资源，不过现代计算机还是能够胜任。但是，这种图的邻接矩阵的大小规模达到了百万的三次方的100倍（1020）。对于当前的技术而言，存储和处理如此巨量的数据是力所不及的。但是，Web图是稀疏图，从一个顶点出发的边的平均数量小于100。因此，Web图的邻接列表的内存需求大约为1012（万亿级）。这个规模对于笔记本计算机来说可能过于庞大，但对于最前沿的数据处理系统而言，还是在它的能力范围之内的。
1.4.4 小测验1.2和小测验1.3的答案
小测验1.2的答案
正确答案：（c）。邻接列表表示形式所需要的空间与图的大小（即顶点的数量加上边的数量）呈线性关系，是比较理想的。要理解这一点略有难度，我们逐个观察它的4个组成部分。顶点数组和边数组的长度分别是n和m，分别需要Θ (n)和Θ (m)的空间。第3个组成部分将两个指针与每条边相关联（每个顶点与一个指针关联），这2m个指针产生了额外的Θ (m)的空间需求。
第4个组成部分可能会令我们感到困惑。无论怎样，总共n个顶点中的每一个顶点均可以参与到多达n−1条的边中，即可以与其他的每个顶点形成一条边，因此看上去会导致空间需求的上界为Θ (n2)。这种平方级的上界对于极为稠密的图而言是准确的，但对于稀疏图来说却显得过大了。关键在于：对于第4个组成部分中的每个“顶点→边”指针，在第3个组成部分中都存在一个对应的“边→顶点”指针。如果边e指向顶点v，那么边e就有一个指向这个顶点v的指针。反之，顶点v也有一个指向它的关联边e的指针。我们可以得出结论，即第3个组成部分和第4个组成部分中的指针具有一对一的对应关系，因此它们需要相同数量的空间，也就是Θ (m)。最终的空间需要：
无论图是否为连接图，以及图是否具有平行边，这个Θ (m+n)的上界均适用。
小测验1.3的答案
正确答案：（d）。邻接矩阵的一种简单存储方法是一个n×n的二维位数组，这需要Θ (n2)的空间，不过还有一个较小的隐藏常量因子。对于稠密图，边的数量接近于n的平方，邻接矩阵所需要的空间大致与图的大小呈线性关系。但是，对于边的数量大致与n呈线性关系的稀疏图，邻接矩阵表示形式太浪费空间了。