1.2 图的存储与遍历

1.2.1 邻接矩阵与关联矩阵

作为一种常见的数据结构，在计算机里图的存储表示方法有很多种，本节只着重介绍邻接矩阵（Adjacency matrix）和关联矩阵（Incidence matrix）这两种方式。

设图G=（V，E），在这里我们对边重新进行了编号e1，e2，…，eM，如图1-7所示。我们用邻接矩阵A描述图中顶点之间的关联，A∈RN×N，其定义为：

图1-7 图G示例

用邻接矩阵存储图的时候，我们需要一个一维数组表示顶点集合，需要一个二维数组表示邻接矩阵。需要特别说明的是，由于在实际的图数据中，邻接矩阵往往会出现大量的0值，因此可以用稀疏矩阵的格式来存储邻接矩阵，这样可以将邻接矩阵的空间复杂度控制在O（M）的范围内。图1-8中a图给出了图G的邻接矩阵存储表示，通过该图可以看出，无向图的邻接矩阵是沿主对角线对称的，即Aij=Aji。

图1-8 图G的邻接矩阵和关联矩阵

除了邻接矩阵外，我们有时也用关联矩阵B∈RN×M来描述节点与边之间的关联，定义如下：

用关联矩阵存储图的时候，我们需要两个一维数组分别表示顶点集合和边集合，需要一个二维数组表示关联矩阵。同样，关联矩阵也可以用稀疏矩阵来存储，这是因为B的任意一列仅有两个非0值。图1-8中b图展示了用关联矩阵来存储图的示例。