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.

Edge List Graph class:

• List of vertices
• List of edges

Edge List Vertex class:

• Data/element x
• Position of vertex in graph's vertex list (in practice, this is a pointer to a linked list node)

Edge List Edge class:

• Data/element x
• List of vertex objects associated with edge e (the two endpoints)
• Position of edge in graph's edge list (in practice, this is a pointer to a linked list node)

Adjacency List

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 below illustrates 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:

Adjacency List Graph class:

• List of all edges on graph
• List of all vertices on graph

Adjacency List Vertex class:

• Data/element x
• Vertex incidence list (list of edges that connect to this vertex)
• Position of vertex in graph's vertex list (pointer to linked list node)

Adjacency List Edge class:

• Data/element x
• Position of edge in graph's edge list (pointer to linked list node)

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.

Adjacency Map Graph class:

• List of all vertices on graph
• List of all edges on graph

Adjacency Map Vertex class:

• Data/element x
• Vertex adjacency map (mapping from keys (list of vertices connected to this vertex) to values (edges that connect the two vertices))
• Position of vertex in graph's vertex list (pointer to linked list node)

Adjacency Map Edge class:

• Data/element x
• Reference to position in the list of edges (?) (linked list node pointer)

Adjacency Matrix

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.

Adjacency Matrix Graph class:

• List of all vertices on graph
• List of all edges on graph
• Adjacency Matrix

Adjacency Matrix Vertex class:

Adjacency Matrix Edge class: