6-4-3 链式邻接表

邻接表表示法（链式）

• 顶点：
  • 按编号顺序将顶点数据存储在一维数组中
• 关联同一顶点的边（以顶点为尾的弧）：
  • 用线性链表存储

特点：

• 邻接表不唯一
• 若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图
• 无向图中顶底$v_i$的度为第i个单链表中的结点数

6-4-3 链式邻接表（2）

有向图链式邻接表

特点：

• 顶点$v_i$的出度为第i个单链表中的结点个数
• 顶点$v_i$的入度为整个单链表中邻接点域值是i-1的结点个数

6-4-3 链式邻接表（3）

链式邻接表的实现