Implementation of Adjacency List Graph: Do incidence of vertices require separate objects?

Question

In Goodrich and Tamassia's textbook: Data Structures & Algorithms in Java, The Adjacency List Structure implementation of the graph ADT is shown in the diagram below:

An Incident object I(u), containing the list of incident edges to Vertex u, is referenced to in the Vertex u object. This is the case for every Vertex in the graph.

My question is, in a Java implementation of this ADT, what is the point in a separate Incident Object, I(u)?

Why can't incident edges be stored in a field in the Vertex object? I can't see how this would be problematic, and surely it would simplify the implementation?

Answer 1

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

They can, not that it makes a particularly big difference either way. There may be restricting implementations, such as when you have an array of primitives which are your vertices, or the vertices are simply represented by an index, i.e. there is no vertex object (this could be done for efficient memory usage when no object is required, for example) - in this case, you'll need to put the incidence object elsewhere.

I can't say for sure what the authors actually meant (assuming they don't say elsewhere in the book - I didn't check), but it's entirely possible that the arrow from the vertex to the incident object means that the Vertex class contains a reference to the incident object (i.e. has a member being the incident object), i.e. the image already represents the way you think it should work.

Answer 2

Yes it is possible, but it would not be adjacency list implementation. A problem with this implementation is when a new edge is inserted into an empty graph, it doesn't add the terminal vertices to V. The method insertEdge should call insertVertex or before to call insertEdge it is needed to call insertVertex.