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

Main article: Graphs/Java/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

Main article: Graphs/Java/Adjacency List

The adjacency list maintains a list pointing to each vertex, and each vertex points to a list of edges that are incident to that vertex. This makes going from a vertex to a set of edges that connect to it very easy. In this context, we say that the vertex v has an associated incidence collection (the list of edges that are incident to that vertex).

The figure shows that the adjacency list stores everything the same way the edge list stores things, plus augments it by adding a list of edges to each vertex object. The Edge and Vertex classes described above are re-used, with the only additional augmentation being:

Vertex objects:

• Reference to incidence list

Adjacency Map

Main article: Graphs/Java/Adjacency Map

Similar approach to adjacency list, but replaces the edge list with a map. The keys are other vertices connected to this vertex, and values are the edges that connect the two vertices.

Vertex objects are augmented as follows:

• Reference to data element x
• Reference to position of vertex instance in list V
• Map of vertices to edges (incidence collection/adjacency map)
• Boolean indicating whether the map is directed or undirected
  • If graph is directed, vertex will store two maps (incoming and outgoing edges)
  • If graph is undirected, incoming and outgoing maps point to the same place

Edge objects are augmented as follows:

• Reference to data element x
• Reference to vertex objects at endpoints of edge
• Reference to position in the list of edges

Adjacency Matrix

Main article: Graphs/Java/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.