Adjacency list

Adjacency list is a fundamental concept in computer science and graph theory used to represent graphs. This data structure allows for a compact representation of graphs, making it an essential tool for various computational algorithms. An adjacency list describes the neighbors of each vertex in a graph, making it an efficient way to store and access connections between nodes in sparse graphs.

Definition

In an adjacency list, a graph is represented as an array or a list of lists. Each entry in this array (or list) corresponds to a vertex in the graph. For each vertex, there is a list that contains the neighbors of that vertex. This means that for a graph G = (V, E), where V is the set of vertices and E is the set of edges, the adjacency list for vertex v is a list of vertices that are adjacent to v.

Advantages

The primary advantage of an adjacency list is its space efficiency in representing sparse graphs, where the number of edges is much less than the square of the number of vertices. It also allows for efficient iteration over the neighbors of a vertex, which is a common operation in many graph algorithms.

Disadvantages

The main disadvantage of an adjacency list is that it can be less efficient for dense graphs, where the number of edges is close to the square of the number of vertices. Additionally, checking for the existence of a specific edge between two vertices can be less efficient than with other representations, such as an adjacency matrix.

Applications

Adjacency lists are widely used in the implementation of graph algorithms, such as depth-first search, breadth-first search, and Dijkstra's algorithm. They are also used in networking applications to represent connections between entities, in social networks to represent relationships between people, and in web crawling to represent links between web pages.

Implementation

An adjacency list can be implemented in several ways, including arrays, linked lists, or a hash table. The choice of implementation depends on the specific requirements of the application, such as the need for fast addition or removal of edges, or the expected sparsity of the graph.

Example

Consider a simple undirected graph with vertices A, B, C, and D, and edges AB, AC, BD, and CD. The adjacency list representation of this graph would be:

• A: B, C
• B: A, D
• C: A, D
• D: B, C

This representation indicates that vertex A is connected to vertices B and C, vertex B is connected to vertices A and D, and so on.

See Also

• Graph theory
• Graph (abstract data type)
• Adjacency matrix
• Incidence matrix
• Depth-first search
• Breadth-first search