Adjacency list: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Adjacency list''' --- список смежности. In an '''adjacency list''' representation of a graph, each vertex has an assoc...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Adjacency list''' | '''Adjacency list''' — ''[[список смежности]].'' | ||
In an '''adjacency list''' representation of a graph, each vertex has an | In an '''adjacency list''' representation of a [[graph, undirected graph, nonoriented graph|graph]], each [[vertex]] has an | ||
associated list of its adjacent vertices. Their lists can be embodied in a table <math>T</math>. | associated list of its [[adjacent vertices]]. Their lists can be embodied in a table <math>T</math>. | ||
In order to trace the list for <math>v_{i}</math>, say, in the | In order to trace the list for <math>v_{i}</math>, say, in the | ||
table, we consult <math>T(i,2)</math> which points to <math>T(T(i,2),1)</math>, where the | table, we consult <math>T(i,2)</math> which points to <math>T(T(i,2),1)</math>, where the | ||
| Строка 11: | Строка 11: | ||
the vertices adjacent to <math>v_{i}</math> within <math>v_{i}</math>'s adjacency list; this | the vertices adjacent to <math>v_{i}</math> within <math>v_{i}</math>'s adjacency list; this | ||
is relevant to understanding some later examples of applying | is relevant to understanding some later examples of applying | ||
algorithms. Clearly, <math>T</math> has <math>(n + |E|)</math> rows for a directed graph and | algorithms. Clearly, <math>T</math> has <math>(n + |E|)</math> rows for a [[directed graph]] and | ||
<math>(n + 2|E|)</math> for an undirected graph. In some circumstances it is | <math>(n + 2|E|)</math> for an undirected graph. In some circumstances it is | ||
additionally useful to use doubly linked lists for undirected graphs; | additionally useful to use doubly linked lists for undirected graphs; | ||
we might also link the two occurrences of an edge <math>(u,v)</math>, the first | we might also link the two occurrences of an [[edge]] <math>(u,v)</math>, the first | ||
in <math>u</math>'s adjacency list and the second in <math>v</math>'s. | in <math>u</math>'s adjacency list and the second in <math>v</math>'s. | ||
Текущая версия от 11:45, 8 ноября 2011
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.