Breadth first search: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Breadth first search''' --- поиск в ширину. Given the adjacency lists <math>A(v)</math> for each vertex <math>v</math> of a connected graph (directe…»)
 
Нет описания правки
 
Строка 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.

Текущая версия от 16:31, 23 октября 2018

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.