图—存储及操作（邻接表法）
2019-08-29 本文已影响0人
梦在原点
对于边稀少的图（稀疏图）使用邻接矩阵法会产生大量空间浪费
邻接表法
同样分为两个表：顶点表（采用顺序存储），边表（采用链式存储）
有向图的邻接表
无向图的邻接表
邻接表法的特点
- 若G为无向图，存储空间为：边+二倍顶点
- 若G为无向图，存储空间为：边+顶点
- 邻接表更适合应用于稀疏图
- 若G为无向图，则结点的度为该结点边表的长度
- 若G为有向图，则结点的出度为该结点边表的长度，入度则需要遍历这个边表
- 邻接表不唯一
