Adjacency Set

graph-theory data-structures

Definition

Adjacency Set

An adjacency set is a data structure used to represent a graph as a collection of sets. Formally, for each vertex , the set contains all vertices such that .

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 expected time for checking edge existence and adding new edges, similar to the adjacency matrix, while maintaining the 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 :

The graph is represented as a pair , where the edges are stored as a set of unordered tuples:

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