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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''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.

Навигация