图的表示

算法导论-第三版

图有多种表示方法，比较常用的表示法有邻接链表和邻接矩阵。

根据边的方向，图可以分为无向图和有向图；根据边的权重，图可以分为带权图和不带权图。

对于图$G=(V,E)$，其邻接链表表示由一个包含$|V|$条链表的数组$Adj$所构成，每个结点有一条链表。对于每个结点$u \in V$，邻接链表$Adj[u]$包含所有与结点$u$之间有边相连的结点$v$，即$Adj[u]$包含图$G$中所有与$u$邻接的结点（也可以说，该链表里包含指向这些结点的指针）。由于邻接链表代表的是图的边，在伪代码里，我们将数组$Adj$看做是图的一个属性，就如我们将边集合$E$看做是图的属性一样。因此，在伪代码里，我们将看到$G.Adj[u]$这样的表示。