Adjacency Set

graph-theory data-structures

Definition

Adjacency Set

An adjacency set is a data structure used to represent a graph $G=(V,E)$ as a collection of sets. Formally, for each vertex $v\in V$, the set $Adj\{v\}$ contains all vertices $u$ such that $\{v,u\}\in E$.

Characteristics

Edge Uniqueness: By utilising a set implementation (e.g., hash set) for each vertex’s neighbours, the structure inherently prevents the creation of duplicate edges.

Efficiency: This representation provides $O(1)$ expected time for checking edge existence and adding new edges, similar to the adjacency matrix, while maintaining the $O(|V|+|E|)$ space complexity characteristic of the adjacency list.

Implementation: While theoretically superior for many operations, it is often more complex to implement compared to simple list-based representations and may have higher constant-time overheads due to hash function computations.

Example

Consider a pentagon graph representing a cycle $C_5$:

The graph is represented as a pair $(V,E)$, where the edges are stored as a set of unordered tuples:

$$\begin{array}{rl}V& =\{0,1,2,3,4\}\\ E& =\{\{0,1\},\{1,2\},\{2,3\},\{3,4\},\{4,0\}\}\end{array}$$

This is typically stored as a map where each vertex points to a set of its neighbours:

• $0\to \{1,4\}$
• $1\to \{0,2\}$
• $2\to \{1,3\}$
• $3\to \{2,4\}$
• $4\to \{3,0\}$