|
|
|
|
|
|
|
|
|
|
|
邻接链表指的是为图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点νi的边（对于有向图是以νi为尾的弧）。邻接链表中的结点有表结点和表头结点两种类型，如下所示：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
这些表头结点通常以顺序结构的形式存储，以便随机访问任一顶点及其邻接表。若图用邻接链表来表示，则对应的数据类型可定义如下：
|
|
|
|
|
|
显然，对于有n个顶点、e条边的无向图来说，其邻接链表需要n个头结点和2e个表结点，如下图所示。对于无向图的邻接链表，顶点νi的度恰为第i个邻接链表中表结点的数目。
|
|
|
|
|
|
|
|
下图（b）是下图（a）所示有向图的邻接表。从中可以看出，由于第i个邻接链表中表结点的数目只是顶点νi的出度，因此必须逐个扫描每个顶点的邻接表，才能求出一个顶点的入度。为此，可以建立一个有向图的逆邻接链表，如下图（c）所示。
|
|
|
|
|
|
|
