4625
правок
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. | ||