图的邻接表存储

基本概念

对于顶点我们还是用数组存储，对于边我们用线性链表存储。邻接表的定义分两部分：顶点表（Vertex Table）和边链表（Edge Linked List）。

顶点表定义

typedef struct vnode {
    vertextype data;          // 顶点信息
    Arcnode *firstarc;        // 指向第一条依附该顶点的弧
} vnode, adjlist[MAX_VERTEX_NUM];

边链表定义

#define MAX_VERTEX_NUM 20
 
typedef struct ArcNode {
    int adjvex;               // 该弧所指向的顶点的位置
    struct ArcNode *nextarc;  // 指向下一条弧的指针
    infoType *info;           // 可以存储图中边的权值
} ArcNode;

无向图的邻接表

• 第 i 个顶点的度 = 第 i 个顶点边链表结点个数。
• 图的总度数 = 所有边链表结点个数之和。
• 图的边数 = 所有边链表结点个数之和的一半。

有向图的邻接表

对于有向图，我们可以建立两个表：

1. 出边表（邻接表）：以同一顶点为弧尾的弧用线性链表存储。通过出边表可以计算出出度和图的边数。
2. 入边表（逆邻接表，Inverse Adjacency List）：以同一顶点为终点的弧用线性链表存储。通过入边表可以计算出入度和图的边数。

顶点表存储顶点（按编号顺序），出边表存储从该顶点出发的弧，入边表存储指向该顶点的弧。

邻接表的性质

• 图的邻接表表示是不唯一的，它与边结点的次序有关。
• 无向图的邻接表中第 i 个顶点的度为第 i 个链表中结点的数目。
• 有向图的邻接表中第 i 个链表的结点的数目是第 i 个顶点的出度，而第 i 个顶点的入度需遍历整个链表。可采用逆邻接表建立一个以 vᵢ 顶点为头的弧的表。
• 无向图的边数等于邻接表中边结点数的一半，有向图的弧数等于邻接表中边结点数。

优势

邻接表对于顶点多边少（类树结构）的图可以极大节省空间，同时对于每个顶点的第一个邻接点也可以较方便地找出。

链接到

• 上一个知识点：7.2 图的邻接矩阵存储
• 下一个知识点：7.4 图的深度优先搜索