Adjacency list

Материал из WikiGrapp
Перейти к:навигация, поиск

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 T. In order to trace the list for v_{i}, say, in the table, we consult T(i,2) which points to T(T(i,2),1), where the first vertex adjacent to v_{i} is recorded. Then T(T(i,2),2) points to T(T(T(i,2),2),1), where the second vertex adjacent to v_{i} is recorded, and so on. The list for v_{i} terminates, when a zero pointer is found. Notice the convention of numerically ordering the vertices adjacent to v_{i} within v_{i}'s adjacency list; this is relevant to understanding some later examples of applying algorithms. Clearly, T has (n + |E|) rows for a directed graph and (n + 2|E|) 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 (u,v), the first in u's adjacency list and the second in v's.