图的顺序存储结构(上)：https://developer.aliyun.com/article/1471371

图的邻接表存储结构详解

通常，图更多的是采用链表存储，具体的存储方法有 3 种，分别是邻接表、邻接多重表和十字链表。

本节先讲解图的邻接表存储法。邻接表既适用于存储无向图，也适用于存储有向图。

在具体讲解邻接表存储图的实现方法之前，先普及一个"邻接点"的概念。在图中，如果两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为邻接点。

邻接指的是图中顶点之间有边或者弧的存在。

邻接表存储图的实现方式是，给图中的各个顶点独自建立一个链表，用节点存储该顶点，用链表中其他节点存储各自的临界点。

与此同时，为了便于管理这些链表，通常会将所有链表的头节点存储到数组中（也可以用链表存储）。也正因为各个链表的头节点存储的是各个顶点，因此各链表在存储临界点数据时，仅需存储该邻接顶点位于数组中的位置下标即可。

例如，存储图 1a) 所示的有向图，其对应的邻接表如图 1b) 所示：

图 1 邻接表存储有向图

拿顶点 V1 来说，与其相关的邻接点分别为 V2 和 V3，因此存储 V1 的链表中存储的是 V2 和 V3 在数组中的位置下标 1 和 2。

从图 1 中可以看出，存储各顶点的节点结构分为两部分，数据域和指针域。数据域用于存储顶点数据信息，指针域用于链接下一个节点，如图 2 所示：

图 2 邻接表节点结构

在实际应用中，除了图 2 这种节点结构外，对于用链接表存储网（边或弧存在权）结构，还需要节点存储权的值，因此需使用图 3 中的节点结构：

图 3 邻接表存储网结构使用的节点

图 1 中的链接表结构转化为对应 C 语言代码如下：

#define MAX_VERTEX_NUM 20//最大顶点个数
#define VertexType int//顶点数据的类型
#define InfoType int//图中弧或者边包含的信息的类型
typedef struct ArcNode{
int adjvex;//邻接点在数组中的位置下标
struct ArcNode * nextarc;//指向下一个邻接点的指针
InfoType * info;//信息域
}ArcNode;
typedef struct VNode{
VertexType data;//顶点的数据域
ArcNode * firstarc;//指向邻接点的指针
}VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组
typedef struct {
AdjList vertices;//图中顶点的数组
int vexnum,arcnum;//记录图中顶点数和边或弧数
int kind;//记录图的种类
}ALGraph;

邻接表计算顶点的出度和入度

使用邻接表计算无向图中顶点的入度和出度会非常简单，只需从数组中找到该顶点然后统计此链表中节点的数量即可。

而使用邻接表存储有向图时，通常各个顶点的链表中存储的都是以该顶点为弧尾的邻接点，因此通过统计各顶点链表中的节点数量，只能计算出该顶点的出度，而无法计算该顶点的入度。

对于利用邻接表求某顶点的入度，有两种方式：

1. 遍历整个邻接表中的节点，统计数据域与该顶点所在数组位置下标相同的节点数量，即为该顶点的入度；
2. 建立一个逆邻接表，该表中的各顶点链表专门用于存储以此顶点为弧头的所有顶点在数组中的位置下标。比如说，建立一张图 1a) 对应的逆邻接表，如图 4 所示：

图 4 逆邻接表示意图

对于具有 n 个顶点和 e 条边的无向图，邻接表中需要存储 n 个头结点和 2e 个表结点。在图中边或者弧稀疏的时候，使用邻接表要比前一节介绍的邻接矩阵更加节省空间。

图的十字链表存储结构

与邻接表不同，十字链表法仅适用于存储有向图和有向网。不仅如此，十字链表法还改善了邻接表计算图中顶点入度的问题。

十字链表存储有向图（网）的方式与邻接表有一些相同，都以图（网）中各顶点为首元节点建立多条链表，同时为了便于管理，还将所有链表的首元节点存储到同一数组（或链表）中。

其中，建立个各个链表中用于存储顶点的首元节点结构如图 1 所示：

图 1 十字链表中首元节点结构示意图

从图 1 可以看出，首元节点中有一个数据域和两个指针域（分别用 firstin 和 firstout 表示）：

• firstin 指针用于连接以当前顶点为弧头的其他顶点构成的链表；
• firstout 指针用于连接以当前顶点为弧尾的其他顶点构成的链表；
• data 用于存储该顶点中的数据；

由此可以看出，十字链表实质上就是为每个顶点建立两个链表，分别存储以该顶点为弧头的所有顶点和以该顶点为弧尾的所有顶点。

注意，存储图的十字链表中，各链表中首元节点与其他节点的结构并不相同，图 1 所示仅是十字链表中首元节点的结构，链表中其他普通节点的结构如图 2 所示：

图 2 十字链表中普通节点的结构示意图

从图 2 中可以看出，十字链表中普通节点的存储分为 5 部分内容，它们各自的作用是：

• tailvex 用于存储以首元节点为弧尾的顶点位于数组中的位置下标；
• headvex 用于存储以首元节点为弧头的顶点位于数组中的位置下标；
• hlink 指针：用于链接下一个存储以首元节点为弧头的顶点的节点；
• tlink 指针：用于链接下一个存储以首元节点为弧尾的顶点的节点；
• info 指针：用于存储与该顶点相关的信息，例如量顶点之间的权值；

比如说，用十字链表存储图 3a) 中的有向图，存储状态如图 3b) 所示：

图 3 十字链表存储有向图示意图

拿图 3 中的顶点 V1 来说，通过构建好的十字链表得知，以该顶点为弧头的顶点只有存储在数组中第 3 位置的 V4（因此该顶点的入度为 1），而以该顶点为弧尾的顶点有两个，分别为存储数组第 1 位置的 V2 和第 2 位置的 V3（因此该顶点的出度为 2）。

对于图 3 各个链表中节点来说，由于表示的都是该顶点的出度或者入度，因此没有先后次序之分。

图的邻接多重表存储结构

为了提高在无向图中操作顶点的效率，本节学习一种新的适用于存储无向图的方法——邻接多重表。

注意，邻接多重表仅适用于存储无向图或无向网。

邻接多重表存储无向图的方式，可看作是邻接表和十字链表的结合。同邻接表和十字链表存储图的方法相同，都是独自为图中各顶点建立一张链表，存储各顶点的节点作为各链表的首元节点，同时为了便于管理将各个首元节点存储到一个数组中。各首元节点结构如图 1 所示：

图 1 邻接多重表各首元节点的结构示意图

图 1 中各区域及其功能为：

• data：存储此顶点的数据；
• firstedge：指针域，用于指向同该顶点有直接关联的存储其他顶点的节点。

从图 1 可以看到，邻接多重表采用与邻接表相同的首元节点结构。但各链表中其他节点的结构与十字链表中相同，如图 2 所示：

图 2 邻接多重表中其他节点结构

图 2 节点中各区域及功能如下：

• mark：标志域，用于标记此节点是否被操作过，例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark 域为 0 表示还未被遍历；mark 为 1 表示该节点已被遍历；
• ivex 和 jvex：数据域，分别存储图中各边两端的顶点所在数组中的位置下标；
• ilink：指针域，指向下一个存储与 ivex 有直接关联顶点的节点；
• jlink：指针域，指向下一个存储与 jvex 有直接关联顶点的节点；
• info：指针域，用于存储与该顶点有关的其他信息，比如无向网中各边的权；

综合以上信息，如果我们想使用邻接多重表存储图 3a) 中的无向图，则与之对应的邻接多重表如图 3b) 所示：

图 3 无向图及其对应的邻接多重表

从图 3 中，可直接找到与各顶点有直接关联的其他顶点。比如说，与顶点 V1 有关联的顶点为存储在数组下标 1 处的 V2 和数组下标 3 处的 V4，而与顶点 V2 有关联的顶点有 3 个，分别是 V1、V3 和 V5。