Breadth first search: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Breadth first search''' --- поиск в ширину. Given the adjacency lists <math>A(v)</math> for each vertex <math>v</math> of a connected graph (directe…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Breadth first search''' | '''Breadth first search''' — ''[[поиск в ширину]].'' | ||
Given the adjacency lists <math>A(v)</math> for each vertex <math>v</math> of a connected | Given the adjacency lists <math>A(v)</math> for each [[vertex]] <math>v</math> of a [[connected graph]] (directed or undirected), the following algorithm conducts a | ||
graph (directed or undirected), the following algorithm conducts a | |||
'''breadth first search'''. On completion of the search, each vertex | '''breadth first search'''. On completion of the search, each vertex | ||
has acquired a '''breadth first index (BFI)''' indicating the order in | has acquired a '''breadth first index (BFI)''' indicating the order in | ||
which the vertex was visited. The vertex <math>u</math> is visited first and <math>BFI(u) | which the vertex was visited. The vertex <math>u</math> is visited first and <math>BFI(u) | ||
= 0</math>. | = 0</math>. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 15:37, 20 апреля 2012
Breadth first search — поиск в ширину.
Given the adjacency lists [math]\displaystyle{ A(v) }[/math] for each vertex [math]\displaystyle{ v }[/math] of a connected graph (directed or undirected), the following algorithm conducts a breadth first search. On completion of the search, each vertex has acquired a breadth first index (BFI) indicating the order in which the vertex was visited. The vertex [math]\displaystyle{ u }[/math] is visited first and [math]\displaystyle{ BFI(u) = 0 }[/math].
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.