Breadth first search

Материал из WikiGrapp
Версия от 15:37, 20 апреля 2012; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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.