A graph is a data structure which contains a "web" of elements stored with nodes being connected to each other. The graph data structure can be thought of as an implementation of a finite graph. Graphs typically define the following operations:

• adjacent(a, b): test whether there is a edge from vertex a to vertex b.

• incidentEdges(a): returns all edges which are connected to a.

• insertEdge(a, b, e): adds an edge from a to b.

• removeEdge(a, b): removes the edge from a to b.

• addVertex(a): adds the vertex a to the graph

• removeVertex(a): removes the vertex a from the graph

Additionally if the graph is modelled as a directed graph we can define the following additional operations:

• origin(e): returns the vertex from which the edge e originates.
• destination(e): returns the vertex to which the edge e points to.

Implementation

Types

Edge List

An edge list stores a graph as a collection (typically a list/array) of all edges in the graph. Each edge is stored as a pair (for undirected graphs) or an ordered pair (for directed graphs):

• Undirected: each edge is stored as {u, v}
• Directed: each edge is stored as (u, v) meaning “from u to v”

Additional data (like weights or labels) can be stored alongside each pair.

Use case: very simple to implement, good for sparse graphs where fast adjacency tests are not needed.

Adjacency List

An adjacency list stores, for every vertex, a list of the vertices to which it is adjacent.

For a vertex u, Adj[u] contains all vertices v such that there is an edge u → v (or {u,v} in undirected graphs).

• Stored commonly as a map/dictionary or a vector of vectors.
• Efficient for sparse graphs and retrieving all neighbours of a vertex.

Use case: most common representation in practice; excellent for DFS/BFS, graph algorithms, and sparse graphs.

Adjacency Matrix

An adjacency matrix for a graph with vertices is an matrix where the element at index indicates there is an edge from the node to .

• Uses space.
• Edge existence queries take constant time.

Use case: dense graphs, or algorithms that need extremely fast adjacency checks.

Comparisons

Comparing the different implementations of a graph with vertices and edges with no self loops or parallel edges bounded in .

	Edge List	Adjacency List	Adjacency Matrix
Space
adjacent(a,b)
incidentEdges(a)
insertEdge(a,b,e)
removeEdge(a,b)
addVertex(a)			(amortized)
removeVertex(a)			(amortized)

Where indicates the degree of the vertex .