Graphs/Data Structures

Notes

This page contains notes on data structures useful for graphs. See also Graphs/ADT for the universal methods that graphs should implement.

Graphs are composed of three basic object types:

• Vertex/Node
• Edge
• Graph

This page will cover a few common data structure representations of these objects.

Edge List

A simple and cheap but messy implementation of graphs.

The edge list implementation maintains an unsorted list of Edge objects and a separate unsorted list of vertex objects. Each list element points to a particular edge or particular vertex. The Edge objects themselves contain the pointers to the vertices at the endpoints.

This can be thought of as a sort of bivariate meta-graph: the vertex list composes nodes of one color, the edge list composes nodes of another color, and the edges between them are directed, and dictated by the Edge objects added to the list.

Vertex objects are augmented as follows:

• reference to data element x
• reference to position of vertex instance in list V (allows for easy removal of a Vertex object, given a Vertex object and a Graph object, because we have the index in the Graph object's list of vertices)

Edge objects are augmented as follows:

• reference to data element x
• Reference to all vertex objects associated with edge e (allow for constant-time implementation of methods to get endpoints of a vertex, or to get opposite vertex given a vertex and an edge)
• Reference to position in edge list (allowing easy/efficient removal of an Edge object, given the Edge object and a Graph object)