【数据结构】图—图的存储结构（邻接矩阵法、邻接表法、邻接多重法、十字链表法）

1 邻接矩阵法

主要存储的是点，所以空间复杂度和点(v)有关
对象：稠密图、有向图、无向图

• 表示唯一、适合稠密图
• 空间复杂度：O（v^2）
• 无向图邻接矩阵一定是一个对称矩阵且唯一。
• 优点：便于判断顶点之间是否有边、便于计算各顶点的度。
• 缺点：增加，删除顶点不方便、统计边的数目不方便、空间复杂度高。

2 邻接表法

对象：稀疏图、链式存储结构。
存放顶点、存放边。另外注意还有逆邻接表的概念。

• 表示不唯一、适合稀疏图
• 时间复杂度O（ v+e ）
• 优点：便于增加，删除顶点、便于统计边的数目、空间效率高
• 缺点：不便判断顶点之间是否有边、不便计算各顶点的度
• G1、G2的邻接表和逆邻接表如下：

3 十字链表法

对象：有向图、 表示不唯一

• 能确定一个图
• 时间复杂度和邻接表相同：O（ v+e ）
• 很容易求的顶点的入度和出度。
• 有向图的十字链表法：
  

4邻接多重法

对象：无向图、链式存储

• 无向图Ｇ2的邻接多重表法：