'''Поиск в ширину''' ('''BFS''', Breadth-first search) — метод один из простейших алгоритмов обхода и разметки вершин графа, являющийся основой для многих важных алгоритмов для работы с графами. Например, алгоритм [[Алгоритм Прима|Прима]] поиска минимального остовного дерева или алгоритм [[Алгоритм Дейкстры|Дейкстры]] поиска кротчайшего пути из одной вершины используют идеи, сходные идеями, используемыми при поиске в ширину.
==Алгоритм==
===Общая идея===
Поиск Пусть задан граф <tex>G = (V, E)</tex> и выделена исходная вершина <tex>s</tex>. Алгоритм поиска в ширину систематически обходит все ребра <tex>G</tex> для "открытия" всех першин, достижимых из <tex>s</tex>, вычисляя при этом расстояние (минимальное количество ребер) от <tex>s</tex> до каждой достижимой из <tex>s</tex> вершины. Кроме того, в процессе обхода строится "дерево поиска в ширину реализуется " с помощью структуры очередькорнем <tex>s</tex>, содержащее все достижимые вершины. Для этого занесем каждой достижимой их <tex>s</tex> вершины <tex>v</tex> путь в очередь исходную вершинудереве поиска в ширину соответствует кратчайшему поти от <tex>s</tex> до <tex>v</tex> в <tex>G</tex>. Затем Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, пока очередь не пустасерый и черный цвета. Изначально все вершины белые, будем извлекать первый элемент из очереди и добавлять позже они могут стать серыми, а затем черными. Когда вершина '''открывается''' в конец процессе поиска, она окрашивается. Таким образом, серые и черные вершины — это вершины, которые уже были открыты, но алгоритм поиска в ширину по-разному работает с ними, чтобы обеспечить объявленный порядок обхода. Если <tex>(u, v) \in E</tex> и вершина <tex>u</tex> черного цвета, то вершина <tex>v</tex> либо серая, либо черная, т.е. все не посещенные вершины, смежные с ним ней уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами. Поиск в ширину стоит дерево поиска в ширину, которое изначально состоит из одного корня, которым является исходная вершина <tex>s</tex>. Если в процессе сканирования списка смежности уже открытое вершины<tex>u</tex> открывается белая вершина <tex>v</tex>, то вершина <tex>v</tex> и ребро <tex>(u, v)</tex> добавляются в дерево. При этом <tex>u</tex> является '''предшественником''' (predecessor), или '''родителем''' (parent), <tex>v</tex> в дереве поиска вширь. Посколько вершина модет быть открыта не более одного раза, она имеет не более одного родителя.
=== Реализация===
Входные данные:Приведенная ниже процедура поиска в ширину '''BFS''' предполагает, что входной граф <tex>G = (V, E)</tex> представлен при помощи списков смежности. Кроме того, поддерживаются дополнительные структуры данных в каждой вершине графа. Цвет каждой вершины <tex>u \in V</tex> хранится в переменной <tex>color[u]</tex>, а предшественник — в переменной <tex>p[u]</tex>. Если прежшественника у <tex>u</tex> нет, то <tex>p[u] =</tex> NIL. Расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится в поле <tex>d[u]</tex>. Алгоритм использует очередь <tex>Q</tex> для работы с множеством серых вершин. '''BFS'''(<tex>G</tex>, <tex>s</tex>) 1 '''for''' (для) каждой вершины <tex>u \in V[G] - s</tex> 2 '''do''' vector < vectortex>color[u] \leftarrow<int/tex> WHITE 3 <tex> g; d[u] \leftarrow \mathcal {1}</tex> 4 <tex>p[u] \leftarrow</ граф, реализованный с помощью списка смежностиtex> NIL 5 int n; <tex>color[s] \leftarrow</tex> GRAY 6 <tex>d[s] \leftarrow</ число вершинtex> 0 7 int <tex>p[s; ] \leftarrow</tex> NIL 8 <tex>Q \leftarrow</ стартовая вершина tex> Ø 9 ENQUEUE(вершины везде нумеруются с нуля<tex>Q</tex>, <tex>s</tex>) 10 '''while''' <tex>Q \ne </tex>Ø 11 '''do''' <tex>u \leftarrow</tex> DEQUEUE(<tex>Q</ чтение графаtex>) 12 '''for''' (для) каждой <tex>м \in Adj[u]</tex> 13 '''do''' '''if''' <tex>color[u] =</tex> WHITE 14 '''then''' <tex>color[v] \leftarrow</tex> GRAY 15 <tex>d[v] \leftarrow d[u] + 1</tex> 16 <tex>p[v] \leftarrow u</tex> 17 ENQUEUE(<tex>Q</tex>, <tex>v</tex>) ... 18 <tex>color[u] \leftarrow</tex>BLACK
Сам обход:== Анализ == queueОценим время работы для входного графа <inttex> q; qG = (V, E)</tex>. После инициализации ни одна вершина не окрашивается в белый цвет, поэтому проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза.push Операции внесения в очередь и удаления из нее требуют <tex>O(s1); vector<bool/tex> времени, так что общее время операций с очередью составляет <tex> used O(nV); used[s] = true; while (!q</tex>. Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза.emptyТак как сумма длин всех списков смежности равна <tex> \Theta (E)) { int v = q.front</tex>, общее время, необходимое для сканирования списков, равно <tex>O(E); q</tex>.popНакладные расходы на инициализацию равны <tex>O(V); for (size_t i=0; i<g[v].size/tex>, так что общее время работы процедуры '''BFS''' составляет <tex>O(); +V +iE) { int to = g[v][i]; if (!used[to]) { used[to] = true; q</tex>.push (to); } } }== Практические применения ==* Волновой алгоритм Таким образом, время работы поиска в трассировке печатных плат;* Поиск увеличивающего пути в Форда-Фалкерсона алгоритм|алгоритме Форда-Фалкерсон (алгоритм Эдмондса-Карпа)ширину линейно зависит от размера представления графа <tex>G</tex> с использованием списков смежности.
== Литература ==
* Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Поиск в ширину // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 215-218. — ISBN 0-201-74395-7
*Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
