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)

Adjacency List

The adjacency list maintains a list for each vertex that contains a list of edges incident to that vertex. This makes it easy to to from a vertex to a set of edges that connect to it.

Adjacency Map

This is a similar approach to the adjacency list, but uses a map to relate vertices to edges that are incident to that vertex. Vertices act as the keys, and a list of edges are the values.

Adjacency Matrix

Provides fast access to specific edges by maintaining a matrix with a row and column entry for each vertex. The entry at (u,v) is the edge (if any) connecting vertex u to vertex v.