6-4-2 邻接表（2)

邻接表特点

• 方便找任一顶点的所有“邻接点”
• 节约稀疏图的空间
  • 需要N个头指针+2E个结点（每个结点至少两个域）
• 方便计算任一顶点的“度”？
  • 对无向图：是的
  • 对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”
• 不方便检查任意一对顶点间是否存在边

邻接矩阵与邻接表表示法的关系

1. 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数
2. 区别：
   1. 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）
   2. 邻接矩阵的空间复杂度为$O(n^2)$，而邻接表的空间复杂度为$O(n+e)$
3. 用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图

6-4 十字链表—用于有向图

十字链表

• 十字链表（Orthogonal List）是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表
• 有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点

• 顶点结点：
  • firstin：存储入度结点的链表
  • firstout：存储出度结点的链表