Adjacency list

In graph theory , adjacency lists (or neighborhood lists ) are a way of representing graphs . A list, the adjacency list, of all of its neighbors (in undirected graphs) or successors (in directed graphs ) is specified for each node . Data structures for graphs are often based on adjacency lists. In the simplest case, a simply linked list of all neighbors is stored in an array for each node .

definition

In an undirected graph , an adjacency list for a node is a list of all neighbors of , i. H. a list of nodes . ${\ displaystyle G = \ left (V, E \ right)}$ ${\ displaystyle v \ in V}$ ${\ displaystyle v}$ ${\ displaystyle \ left \ {v '\ in V: \ {v, v' \} \ in E \ right \}}$

In a directed graph , an adjacency list for a node is a list of all descendants of , i.e. H. a list of nodes . ${\ displaystyle G = \ left (V, E \ right)}$ ${\ displaystyle v \ in V}$ ${\ displaystyle v}$ ${\ displaystyle \ left \ {v '\ in V: (v, v') \ in E \ right \}}$

In both cases, the order of the nodes in the adjacency list is arbitrary. An adjacency list representation of a graph is obtained by specifying an adjacency list for each node.

example 1

An undirected graph with nodes and edges , and its representation with the help of adjacency lists. ${\ displaystyle V = \ {a, b, c, d, e \}}$ ${\ displaystyle E = {\ {a, b \}, \ {a, d \}, \ {a, d \}, \ {a, e \}, \ {b, c \}, \ {c , d \} \}}$

graph	Adjacency lists
	a: d, b, d, e b: c, a c: b, d d: a, a, c e: a

Example 2

A directed graph with nodes and edges , and its representation with the help of adjacency lists. ${\ displaystyle V = \ {a, b, c, d, e \}}$ ${\ displaystyle E = \ {(a, b), (a, d), (a, e), (b, c), (c, d), (d, a) \}}$

graph	Adjacency lists
	a: b, d, e b: c c: d d: a e:

Adjacency lists as data structures

The adjacency list representation of graphs often serves as the basis of data structures for graphs. There are different ways of implementing this adjacency list representation in a data structure, which also cause the data structures to behave differently.

Some variants:

Node array with adjacency lists as linked lists : An array indexed with node identifiers is stored here, with a pointer to the corresponding adjacency list being stored in each element of the array . The adjacency lists themselves are saved as linked lists.
Linked list of nodes with adjacency lists as linked lists: The nodes are stored as a linked list and each node contains a pointer to the corresponding adjacency list. The adjacency lists themselves are also saved as linked lists.

Using a naive array implementation, an adjacency list for an undirected graph requires approximately bytes of storage , where is the number of edges of the graph. In the adjacency matrix, the main alternative to the adjacency list, each entry in the adjacency matrix only needs one bit. An adjacency matrix can therefore be represented very compactly in only bytes of contiguous memory, the number of nodes in the graph being. This compactness also promotes the locality of the references . However, for a thin graph, adjacency lists require less storage space. If one takes into account that an undirected simple graph can have at most edges, which allows loops, one can denote the density of the graph with . Then if , ie the representation as an adjacency list takes up more space than the representation as an adjacency matrix, if . Therefore, a graph must be thin enough so that a representation of the adjacency list is more compact than a representation as an adjacency matrix. ${\ displaystyle 2 \ cdot {\ tfrac {32} {8}} \ cdot | E | = 8 \ cdot | E |}$ ${\ displaystyle | E |}$ ${\ displaystyle {\ tfrac {| V | ^ {2}} {8}}}$ ${\ displaystyle | V |}$ ${\ displaystyle | V | ^ {2}}$ ${\ displaystyle d = {\ tfrac {| E |} {| V | ^ {2}}}}$ ${\ displaystyle 8 \ cdot | E |> {\ tfrac {| V | ^ {2}} {8}}}$ ${\ displaystyle {\ tfrac {| E |} {| V | ^ {2}}}> {\ tfrac {1} {64}}}$ ${\ displaystyle d> {\ tfrac {1} {64}}}$

The different representations also facilitate different operations . Finding all the neighboring nodes of a given node with adjacency lists is as easy as reading the corresponding adjacency list and is therefore proportional to degree . In the case of an adjacency matrix, an entire row must be read instead and therefore proportional to the total number of nodes. Whether there is an edge between two given nodes can be determined directly from the adjacency matrix, while adjacency lists require a running time proportional to the minimum degree of the two nodes.

Examples

Node array with adjacency lists as singly linked lists

graph	Adjacency lists	Data structure
	a: d, b, d, e b: c, a c: b, d d: a, a, c e: a
	a: b, d, e b: c c: d d: a e:

Node array with adjacency lists as doubly linked lists

graph	Adjacency lists	Data structure
	a: d, b, d, e b: c, a c: b, d d: a, a, c e: a
	a: b, d, e b: c c: d d: a e:

Linked list of nodes with adjacency lists as singly linked lists

graph	Adjacency lists	Data structure
	a: d, b, d, e b: c, a c: b, d d: a, a, c e: a
	a: b, d, e b: c c: d d: a e:

literature

Robert Sedgewick , Kevin Wayne: Algorithms: Algorithms and Data Structures . 4th edition. Hallbergmoos: Pearson, 2014, ISBN 978-3-86894-184-5 , pp. 559-563 .

Thomas H. Cormen, Charles Leiserson , Ronald L. Rivest , Clifford Stein: Introduction to Algorithms . 3. Edition. MIT Press and McGraw-Hill, 2009, ISBN 978-0-262-53305-8 , pp. 589-593 .

Web links

Wikiversity: Algorithms and Data Structures / Representation of Graphs - Course Materials

Commons : Adjacency list - collection of images, videos and audio files

Eric W. Weisstein : Adjacency List . In: MathWorld (English).