Adjacency list

Adjacency list — список смежности.

In an adjacency list representation of a graph, each vertex has an associated list of its adjacent vertices. Their lists can be embodied in a table [math]\displaystyle{ T }[/math]. In order to trace the list for [math]\displaystyle{ v_{i} }[/math], say, in the table, we consult [math]\displaystyle{ T(i,2) }[/math] which points to [math]\displaystyle{ T(T(i,2),1) }[/math], where the first vertex adjacent to [math]\displaystyle{ v_{i} }[/math] is recorded. Then [math]\displaystyle{ T(T(i,2),2) }[/math] points to [math]\displaystyle{ T(T(T(i,2),2),1) }[/math], where the second vertex adjacent to [math]\displaystyle{ v_{i} }[/math] is recorded, and so on. The list for [math]\displaystyle{ v_{i} }[/math] terminates, when a zero pointer is found. Notice the convention of numerically ordering the vertices adjacent to [math]\displaystyle{ v_{i} }[/math] within [math]\displaystyle{ v_{i} }[/math]'s adjacency list; this is relevant to understanding some later examples of applying algorithms. Clearly, [math]\displaystyle{ T }[/math] has [math]\displaystyle{ (n + |E|) }[/math] rows for a directed graph and [math]\displaystyle{ (n + 2|E|) }[/math] for an undirected graph. In some circumstances it is additionally useful to use doubly linked lists for undirected graphs; we might also link the two occurrences of an edge [math]\displaystyle{ (u,v) }[/math], the first in [math]\displaystyle{ u }[/math]'s adjacency list and the second in [math]\displaystyle{ v }[/math]'s.