Викиконспекты - Вклад участника [ru]

Заглавная страница

2021-06-08T10:23:05Z

77.234.215.137:

Добро пожаловать на сайт [[Викиконспекты:Описание|вики-конспектов]]!

= Проверяемые конспекты =

== [[Дискретная математика | Дискретная математика]]==
* [[Дискретная математика#Отношения| Отношения]]
* [[Дискретная математика#Булевы функции| Булевы функции]]
* [[Дискретная математика#Схемы из функциональных элементов| Схемы из функциональных элементов]]
* [[Дискретная математика#Представление информации| Представление информации]]
* [[Дискретная математика#Алгоритмы сжатия| Алгоритмы сжатия данных]]
* [[Дискретная математика#Комбинаторика| Комбинаторика]]
* [[Дискретная математика#Производящая функция|Производящая функция]]

==[[Теория вероятностей | Теория вероятностей]]==

* [[Теория вероятностей # Теория вероятностей| Базовые определения и формулы расчета вероятности]]
* [[Теория вероятностей #Марковские цепи| Марковские цепи]]

==[[Теория формальных языков|Теория формальных языков]]==
* [[Теория формальных языков#Автоматы и регулярные языки|Автоматы и регулярные языки]]
* [[Теория формальных языков#Контекстно-свободные грамматики|Контекстно-свободные грамматики]]

== [[Теория матроидов | Теория матроидов]]==

* [[Теория матроидов#Основные факты теории матроидов | Основные факты]]
* [[Теория матроидов#Пересечение матроидов | Пересечение матроидов]]
* [[Теория матроидов#Объединение матроидов | Объединение матроидов]]

== [[Теория расписаний | Теория расписаний]]==

*[[Теория расписаний#Задачи с одним станком | Задачи с одним станком]]
*[[Теория расписаний#Специальные случаи задач для двух станков | Специальные случаи задач для двух станков]]
*[[Теория расписаний#Задачи для произвольного числа станков | Задачи для произвольного числа станков]]

== [[Теория вычислимости | Теория вычислимости]]==
* [[Теория вычислимости#Разрешимые и перечислимые языки | Разрешимые и перечислимые языки]]
* [[Теория вычислимости#Вычислительные формализмы | Вычислительные формализмы]]
* [[Теория вычислимости#Примеры неразрешимых задач | Примеры неразрешимых задач]]

==[[Теория сложности | Теория сложности]]==
* [[Теория сложности#Детерминированные и недетерминированные вычисления, сложность по времени и по памяти | Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
* [[Теория сложности#Схемная сложность | Схемная сложность]]
* [[Теория сложности#Вероятностные сложностные классы | Вероятностные сложностные классы]]

== [[Алгоритмы и структуры данных | Алгоритмы и структуры данных]]==
* [[Алгоритмы и структуры данных#Амортизационный анализ | Амортизационный анализ]]
* [[Алгоритмы и структуры данных#Персистентные структуры данных | Персистентные структуры данных]]
* [[Алгоритмы и структуры данных#Приоритетные очереди | Приоритетные очереди]]
* [[Алгоритмы и структуры данных#Система непересекающихся множеств | Система непересекающихся множеств]]
* [[Алгоритмы и структуры данных#Поисковые структуры данных | Поисковые структуры данных]]
* [[Алгоритмы и структуры данных#Запросы на отрезках | Запросы на отрезках]]
* [[Алгоритмы и структуры данных#Дерево Фенвика | Дерево Фенвика]]
* [[Алгоритмы и структуры данных#Задача о наименьшем общем предке | Задача о наименьшем общем предке]]
* [[Алгоритмы и структуры данных#Хеширование | Хеширование]]
* [[Алгоритмы и структуры данных#Сортировки | Сортировки]]
* [[Алгоритмы и структуры данных#Сортирующие сети | Сортирующие сети]]
* [[Алгоритмы и структуры данных#Алгоритмы поиска | Алгоритмы поиска]]
* [[Алгоритмы и структуры данных#Динамическое программирование | Динамическое программирование]]
* [[Алгоритмы и структуры данных#Алгоритмы во внешней памяти | Алгоритмы во внешней памяти]]

== [[Теория графов | Теория графов]]==
* [[Теория графов#Основные определения теории графов | Основные определения теории графов]]
* [[Теория графов#Связность в графах | Связность в графах]]
* [[Теория графов#Остовные деревья | Остовные деревья]]
* [[Теория графов#Обходы графов | Обходы графов]]
* [[Теория графов# Укладки графов | Укладки графов]]
* [[Теория графов#Раскраски графов | Раскраски графов]]
* [[Теория графов#Обход в глубину | Обход в глубину]]
* [[Теория графов#Кратчайшие пути в графах | Кратчайшие пути в графах]]
* [[Теория графов#Задача о паросочетании | Задача о паросочетании]]
* [[Теория графов#Задача о максимальном потоке | Задача о максимальном потоке]]
* [[Теория графов#Задача о потоке минимальной стоимости | Задача о потоке минимальной стоимости]]
* [[Теория графов#Cлучайные графы | Cлучайные графы]]

== [[Алгоритмы на строках | Алгоритмы на строках]]==
* [[Алгоритмы на строках# Поиск подстроки в строке | Поиск подстроки в строке]]
* [[Алгоритмы на строках#Суффиксное дерево |Суффиксное дерево]]
* [[Алгоритмы на строках#Суффиксный массив | Суффиксный массив]]

== [[Методы трансляции | Методы трансляции]] ==
* [[Методы трансляции#Нисходящий разбор|Нисходящий разбор]]
* [[Методы трансляции#Восходящий разбор | Восходящий разбор]]

== [[Вычислительная геометрия|Вычислительная геометрия ]]==
* [[Вычислительная геометрия#Основание вычислительной геометрии|Основание вычислительной геометрии]]
* [[Вычислительная геометрия#Вычисление геометрических предикатов|Вычисление геометрических предикатов]]
* [[Вычислительная геометрия#Пересечение отрезков|Пересечение отрезков]]
* [[Вычислительная геометрия#Выпуклые оболочки|Выпуклые оболочки]]
* [[Вычислительная геометрия#Поиск|Поиск]]
* [[Вычислительная геометрия#Триангуляция|Триангуляция]]
* [[Вычислительная геометрия#ППЛГ и РСДС|ППЛГ и РСДС]]
* [[Вычислительная геометрия#Алгоритмы локализации|Алгоритмы локализации]]
* [[Вычислительная геометрия#Триангуляция Делоне и диаграмма Вороного|Триангуляция Делоне и диаграмма Вороного]]
* [[Вычислительная геометрия#Планирование движения (Motion planning)|Планирование движения (Motion planning)]]

== [[Язык программирования Java|Язык программирования Java]]==
*[[Основная информация о языкe]]
*[[Программирование по контракту]]
*[[Обработка ошибок и исключения]]
*[[Generics]]
*[[Перечисления]]

== [[Параллельное программирование|Параллельное программирование]]==
*[[Очередь Майкла и Скотта]]

== [[Машинное обучение|Машинное обучение]]==

*[[Модель алгоритма и ее выбор]]
*[[Переобучение]]
*[[Кросс-валидация]]
*[[Выброс]]
*[[Машинное обучение|Другие темы]]

= Непроверяемые конспекты =

*[[Алгебра и геометрия 1 курс | Алгебра и геометрия — 1, 2 семестр]]
*[[Математический анализ 1 курс | Математический анализ — 1, 2 семестр]]
*[[Математический анализ 2 курс | Математический анализ — 3, 4 семестр]]
*[[Математическая логика|Математическая логика — 3 семестр]]
*[[Участник:Qwerty787788/плюсы3сем | С++ — 2, 3 семестр]]
*[[Дифференциальные уравнения | Дифференциальные уравнения — 3 семестр]]
*[[Assembler|Assembler — 4 семестр]]
*[[Алгоритмы алгебры и теории чисел|Алгоритмы алгебры и теории чисел — 4 семестр]]
*[[Функциональный_анализ_3_курс | Функциональный анализ — 5, 6 семестр]]
*[[Параллельное программирование|Параллельное программирование — 6 семестр]]
*[[Базы данных|Базы данных — 7 семестр]]
*[[Компьютерные сети|Компьютерные сети — 7, 8 семестр]]
*[[Эволюционные алгоритмы|Эволюционные алгоритмы — 10 семестр]]

[[Категория:Всё]]

Заглавная страница

2021-06-08T10:22:41Z

77.234.215.137: Полностью удалено содержимое страницы

Обход в ширину

2021-06-08T10:15:11Z

77.234.215.137: /* Описание алгоритма */

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==
[[Image: Graph-BFS.gif|thumb|240px|Алгоритм BFS 
посещенные вершины ]]

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

Для алгоритма нам потребуются [[Очередь|очередь]] и множество посещенных вершин <tex> was </tex>, которые изначально содержат одну вершину <tex> s </tex>. На каждом шагу алгоритм берет из начала очереди вершину <tex> v </tex> и добавляет все непосещенные смежные с <tex> v </tex> вершины в <tex> was </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работу.

== Анализ времени работы ==
Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.

'''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.

Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у <tex>v</tex> есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до <tex> w </tex> найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

== Вариации алгоритма ==
=== 0-1 BFS ===
Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1 </tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом:

Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве [[#Корректность | расположения элементов в деке в порядке неубывания]] продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

== См. также ==
* [[Обход в глубину, цвета вершин]]
* [[Алгоритм Дейкстры]]
* [[Теория графов]]

== Источники информации ==

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Обход в ширину

2021-06-08T10:13:39Z

77.234.215.137: /* Описание алгоритма */

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==
[[Image: Graph-BFS.gif|thumb|240px|Алгоритм BFS 
посещенные вершины ]]

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

Для алгоритма нам потребуются [[Очередь|очередь]] и миша глазов пидорас посещенных вершин <tex> was </tex>, которые изначально содержат одну вершину <tex> s </tex>. На каждом шагу алгоритм берет из начала очереди вершину <tex> v </tex> и добавляет все непосещенные смежные с <tex> v </tex> вершины в <tex> was </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работу.

== Анализ времени работы ==
Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.

'''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.

Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у <tex>v</tex> есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до <tex> w </tex> найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

== Вариации алгоритма ==
=== 0-1 BFS ===
Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1 </tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом:

Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве [[#Корректность | расположения элементов в деке в порядке неубывания]] продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

== См. также ==
* [[Обход в глубину, цвета вершин]]
* [[Алгоритм Дейкстры]]
* [[Теория графов]]

== Источники информации ==

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]