# Notes

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)

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:

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

• 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)

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

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.

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

• 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)

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

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.