6.2 图的存储

邻接矩阵、邻接表、十字链表与邻接多重表，比较它们的空间开销与适用场景。

邻接矩阵法

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。

对于带权图（网），若顶点之间有边相连，则邻接矩阵中对应项存放着该边对应的权值；若顶点之间不相连，则用 ∞ 来代表这两个顶点之间不存在边。

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct {
    VertexType Vex[MaxVertexNum];               // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵，边表
    int vexnum, arcnum;                         // 图的当前顶点数和边数
} MGraph;

邻接矩阵的特点：

1. 无向图的邻接矩阵一定是一个对称矩阵（并且唯一），因此在实际存储时只需存储上（或下）三角矩阵的元素；
2. 对于无向图，第 $i$ 行（或第 $i$ 列）非零元素的个数正好是顶点 $i$ 的度；
3. 对于有向图，第 $i$ 行非零元素的个数正好是顶点 $i$ 的出度，第 $i$ 列非零元素的个数正好是顶点 $i$ 的入度；
4. 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连；但要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大；
5. 稠密图适合使用邻接矩阵存储，空间复杂度为 $O(n^2)$，与边数无关。

邻接表法

当一个图为稀疏图时，使用邻接矩阵法显然会浪费大量的存储空间。邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。

所谓邻接表，是指对图中的每个顶点 $v_i$ 建立一个单链表，第 $i$ 个单链表中的结点表示依附于顶点 $v_i$ 的边（对于有向图则是以顶点 $v_i$ 为尾的弧），这个单链表就称为顶点 $v_i$ 的边表（有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储，称为顶点表。

typedef struct ArcNode {         // 边表结点
    int adjvex;                  // 该弧所指向的顶点的位置
    struct ArcNode *nextarc;     // 指向下一条弧的指针
    // InfoType info;            // 网的边权值
} ArcNode;
typedef struct VNode {           // 顶点表结点
    VertexType data;             // 顶点信息
    ArcNode *firstarc;           // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices;            // 邻接表
    int vexnum, arcnum;          // 图的顶点数和弧数
} ALGraph;

邻接表的特点：

1. 若 $G$ 为无向图，则所需的存储空间为 $O(|V| + 2|E|)$；若 $G$ 为有向图，则所需的存储空间为 $O(|V| + |E|)$。前者的倍数 2 是因为在无向图中，每条边在邻接表中出现了两次；
2. 对于稀疏图，采用邻接表表示将极大地节省存储空间；
3. 在邻接表中，给定一个顶点，能很容易地找出它的所有邻边；但要确定给定的两个顶点间是否存在边，则需要在相应结点对应的边表中查找另一结点，效率较低；
4. 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。也可以采用逆邻接表的存储方式来加速求解给定顶点的入度；
5. 图的邻接表表示并不唯一，因为各边表结点的链接次序可以是任意的。

十字链表

十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。

在十字链表中，既容易找到 $v_i$ 为尾的弧，也容易找到 $v_i$ 为头的弧，因而容易求得顶点的出度和入度。图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。

邻接多重表

邻接多重表是无向图的另一种链式存储结构。在邻接表中，容易求得顶点和边的各种信息，但求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。

与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构为 ivex | ilink | jvex | jlink | (info)，其中 ilink 指向下一条依附于顶点 ivex 的边，jlink 指向下一条依附于顶点 jvex 的边。在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。

四种存储方式的比较

即时练习