数据结构重学日记（二十六）图的存储

图的存储结构相比线性表和树更加复杂：

1. 图中顶点没有次序之分
2. 图中边和顶点的数量任意

图的存储结构可以分为两大类：

1. 邻接矩阵（顺序存储）
2. 邻接表（链式存储）：

1. 十字链表（有向图）
2. 邻接多重表（无向图）

邻接矩阵 无向图

顶点：用一维数组存储
边或弧：用二维数组存储

邻接矩阵

顶点数组：A B C D
边或弧：
A B C D
A 0 1 1 1
B 1 0 1 0
C 1 1 0 1
D 1 0 1 0

行或列中 1 的个数为顶点的度。

无向图的邻接矩阵是一个对称矩阵。也可以只存储一半矩阵以节省存储空间。

邻接矩阵 有向图

与无向图的区别为边是有方向的
A B C D
A 0 1 0 1
B 0 0 1 0
C 1 1 0 1
D 0 0 0 0

从为行，到为列。

邻接表

定点表：存储顶点和第一个邻接点的指针。
边表：每个顶点所有邻接的顶点集。