Adjacency list: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Adjacency list''' --- список смежности. In an '''adjacency list''' representation of a graph, each vertex has an assoc...)
 
Нет описания правки
 
Строка 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.