邻接信息应该存储在图形对象中还是存储在顶点本身中？

Question

为了演示邻接列表的概念，我假设很容易将列表表示为列表的列表，并将顶点表示为数字，然后将它们放在一个数组中，在那里我们可以通过索引直接在图中引用它们。一旦我们得到一个顶点的索引，我们就可以得到相应的列表数组。

然而，对于实际对象，顶点不能仅仅由数组索引引用，我假设需要创建一个单独的顶点对象。在这种情况下，我的问题是边缘信息应该实现在哪里。

在基于面向对象的编程语言（如java）中，我看到了基于邻接列表的图实现的实现，其中邻接信息存储在顶点对象本身中，具有某种类型的数据结构（如数组、列表等）的数据成员。然而，我也看到人们通过维护边列表来实现图对象本身中的邻接边信息。

至于边缘信息应该存储在哪里，这更多的是个人偏好吗？

Answer 1

我认为这取决于您希望图形API看起来是什么样子。

例如，假设该图使用表示顶点的任意泛型类型。在这种情况下，不需要定义内部使用的顶点包装器（并在其中管理邻接），您可以简单地将邻接数据结构作为graph类的成员：

public class Graph<V> {
  private Map<V, Set<V>> adjacencies;
  ..
}  

另一方面，如果您确实希望公开一个顶点对象及其邻接（我没有找到一个很好的理由），那么您应该小心数据一致性。邻接数据必须为调用方只读（或进行防御复制），否则调用方可能会以不对称的方式更改边。