algorithm - 图的邻接表表示

Question

在斯坦福大学的一门算法课程中，教授列出了图的邻接表表示的以下成分：

1. 数组或顶点列表
2. 边的数组或列表
3. 顶点列表中的每个顶点都指向入射在其上的边。
4. 边列表中的每条边都指向它的边点。

这是否对应于维基百科？Goodrich 和 Tamassia 建议的面向对象关联列表结构有特殊的顶点对象和边对象类？

这种表示是否与图表的“发病列表”表示相同？如果是，为什么本文将“邻接表”和“发生表”分开？

Answer 1

我猜这篇文章的作者会将该结构称为关联列表，因为节点通过边而不是直接链接到其他节点。关联列表/邻接列表的区别是非标准的，恕我直言，这并不是非常有用，因为这两种结构具有相似的性能特征，并且如果去掉列表 ADT，则不清楚这种区别是否有根据。