java - 邻接表图的实现 : Do incidence of vertices require separate objects?

Question

在Goodrich和Tamassia的教科书:Data Structures & Algorithms in Java中，图ADT的邻接表结构实现如下图所示:

Incident 对象 I(u)，包含顶点 u 的入射边列表，在 Vertex u 对象中引用。图中的每个顶点都是这种情况。

我的问题是，在这个 ADT 的 Java 实现中，单独的事件对象 I(u) 有何意义？

为什么关联边不能存储在 Vertex 对象的字段中？我不明白这会产生什么问题，而且它肯定会简化实现吗？

Answer 1

Why can't incident edges be stored in a field in the Vertex object?

他们可以，但这并不是说这两种方式都会产生特别大的差异。可能存在限制性的实现，例如当您有一个基元数组作为顶点，或者顶点仅由索引表示时，即没有顶点对象(例如，当不需要对象时，可以这样做以实现高效的内存使用) - 在这种情况下，您需要将关联对象放在其他地方。

我无法确定作者的实际含义(假设他们在书中其他地方没有说 - 我没有检查)，但从顶点到事件对象的箭头完全有可能意味着 Vertex 类包含对事件对象的引用(即有一个成员是事件对象)，即图像已经代表了您认为它应该工作的方式。