图数据的存储

图是一种比较复杂的数据结构，为适应图数据的增删改查，采用的存储结构有邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等。

一 邻接矩阵

用两个数组来表示图，其中一个数组存储顶点信息，另一个二维数组存储边信息，即一个顶点数组和一个边数组，这个二维的边数组存储的就是邻接矩阵。

无向图的邻接矩阵是一个对称矩阵，主对角线为零，行或列的和称为顶点的度。有向图的邻接矩阵则不一定对称。

无向图的邻接矩阵：

有向图的邻接矩阵：

优点：简单直观，适用于稠密图，快速检查两个顶点之间是否有边连接。

缺点：对于稀疏图，浪费了大量存储资源。且在邻接矩阵中添加顶点时必须重新按照新的行或列创建，然后将已有的数据复制到新的矩阵中。

二 邻接链表

邻接链表中，图中的所有顶点采用一个专门的数组存储，每个顶点的临边采用链表存储，链表的起止地址信息也会存储顶点数组中。有向图的临界表中的单链表只存储了出度节点。

邻接表中每个结点的单链表长度就是该节点的出度，带权邻接表只需给边结点增加一个存储权值的数据域即可。

无向图邻接链表：

   1
  / \
 2 - 3
 | /
 4

1: 2 -> 3
2: 1 -> 3 -> 4
3: 1 -> 2 -> 4
4: 2 -> 3

有向图邻接链表：

  1
  ↓
  2 → 3
 ↗ ↙
 4

1: → 2
2: → 3
3: 
4: → 2

优点：适用于稀疏图，节省存储空间；插入或删除边的操作相对较为高效。

缺点：需要额外的空间存储链表，查找节点之间是否有边的操作相对慢。

三 十字链表

十字链表也叫做正交链表，是为了存储有向图专门设计的一种存储结构，综合了邻接表和逆邻接表，多占了一些空间，但计算出度和入度都非常方便，并且创建图的时间复杂度和邻接表相比并没有增加。

每个顶点节点设置两个指针域，一个指向入边表的指针，另一个指向出边表的指针。

   1
 ↗ ↑ ↖
 2  -  3
 ↓  ↘ ↓
 4     5


#节点结构
+-----+
|  1  |
+-----+
| OUT | --> (2, w1) --> (3, w2)
| IN  | --> (2, w3) --> (4, w4) --> (5, w5)
+-----+

#出边表
Outgoing Edge List for Node 1:
(2, w1) --> (3, w2)

#入边表
Incoming Edge List for Node 1:
(2, w3) --> (4, w4) --> (5, w5)

四 邻接多重表

邻接多重表是邻接表针对无向图进一步优化的产物。邻接表对顶点的操作很方便，但对边的操作很不方便，如删掉一条边，由于邻接表中的每一条边都涉及两个顶点，所以删除一条边需要操作两个顶点。

邻接多重表的设计使每一条边都用一个点表示。邻接多重表和十字链表略有相似，都通过边节点结构中的指针域相互指向，使边界点的数目可以等于边的数目，而不是边数目的二倍。