Graph Representation

Notation

We will denote:

Table of contents

Sparse vs Dense Graphs

Real-world graphs are usually sparse. Keep this in mind when choosing a representation.

This is the least common and simplest way to represent a graph.

A graph is simply a list of edges $(u, v)$.

The edges look sorted in the above figure, but in reality, there is no sorting of edges. It really depends on how you add them to the list.

Summary:

Basically a dictionary where the keys are the vertices and the values are list of vertices that are neighbors.

Access to outgoing edges is cheap: $O(1)$
- Hash table lookup of vertex
Access to incoming edges is expensive: $O(|V| + |E|)$
- Go through all vertices and check if an edge exists
Inserting an edge is cheap: $O(1)$
Deleting an edge is expensive: $O(|E|)$
- To delete $(u, v)$, find and delete $v$ from the adjacency list of $u$ (and maybe $u$ from the adjacency list of $v$ in case of an undirected graph)
Space efficient for sparse graphs: $O(|V| + |E|)$

Summary:

Good for sparse graphs, which is common in practice.
Problems in practice require frequent access to neighbors, so a real advantage over list of edges.

Use a matrix of $n \times n$ where $n = |V|$.

Initially, all elements are set to a falsey value. If there is an edge between $u$ and $v$, set m[u][v] to a truthy value.

Access to neighbors: $O(|V|)$
- $\forall v \in V$, go through m[u][v]
Inserting an edge is cheap: $O(1)$
Deleting an edge is cheap: $O(1)$
Not space efficient, since it always reserves space for a complete graph: $O(|V|^2)$

Summary:

References: