邻接表的表示方法
邻接表（Adjacency List） 是图的一种链式存储结构 在邻接表中 对图中每个顶点建立一个单链表 第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧） 邻接表由两部分构成 表头结头 表结点组成的单链表
邻接表的表示意义为 对于图G=(V E) 若(i j)∈E 则第i个表头结点的单链表上有一个adjvex为j的表结头
无向图的邻接表称为边表 有向图的邻接表称为出边表 邻接表的表头向量称为顶点表 逆邻接表在有向图中 对每个顶点vi建立一个链接以vi为头的弧表 逆邻接表在形式上由两部分构成 表头结点 表结点组成的单链表 表头结点与邻接表完全一样 但表结点组成的单链表是不同的 逆邻接表的表示意义为 对于图G=(V E) 若＜i j＞∈E 则第j个表头结点的单链表上有一个adjvex为i的表结头
一个图的邻接矩阵表示是唯一的 而邻接表表示则不是唯一的 稀疏图（Sparse graph） 有很少条边或弧（如e＜nlogn)的图 稠密图（Dense graph） 边很多的图 相比之下 从存储空间角度看 邻接表更适合于表示稀疏图而邻接矩阵适合于表示稠密图 邻接表的C语言描述
邻接表形式说明
lishixinzhi/Article/program/sjjg/201311/23684