adjacenslistor

Adjacenslistor, commonly known in English as adjacency lists, are a widely used data structure for representing graphs. In this representation, each vertex has an associated list of its neighboring vertices. This approach supports both directed and undirected graphs; for a directed graph, the list for a vertex u contains all vertices v such that there is an edge u -> v, while for undirected graphs the edge is stored in the lists of both endpoints.

Implementation details vary, but the core idea is the same: for every vertex v, store a list L(v) of vertices adjacent to v. The lists can be implemented as linked lists, dynamic arrays, or hash-based sets. In undirected graphs, each edge (u, v) is typically represented twice, once in L(u) and once in L(v). In directed graphs, edges are stored only in the source vertex’s list.

Performance characteristics: Space complexity is O(V + E) for a graph with V vertices and E edges, since each edge contributes to one or two entries in the lists depending on direction. Enumerating the neighbors of a vertex v is O(degree(v)). Adding an edge is generally O(1) if the list supports constant-time insertion, but testing whether a specific vertex w is a neighbor of v takes O(degree(v)) time unless the lists are augmented with a hash set or similar structure.

Comparison and use cases: Adjacency lists are favored for sparse graphs because they use memory proportional to the number of edges. They contrast with adjacency matrices, which require O(V^2) space and are less efficient for sparse graphs but allow constant-time edge checks. Common applications include graph traversals (depth-first and breadth-first search), network routing, and social-network analyses.

Example: For a graph with vertices A, B, C and edges A-B, A-C, B-C, the lists could be A: [B, C], B: [A, C], C: [A, B].