Изменения

'''Обход в ширину''' ('''Поиск в ширину, 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>G = (V, серый и черный цвета. Изначально все вершины белыеE)</tex>, и позже они могут стать серыми, а затем черными. Когда в котором выделена исходная вершина '''открывается''' в процессе поиска, она окрашивается<tex>s</tex>. Таким образом, серые и черные вершины — это вершины, которые уже были открытыДля алгоритма нам потребуются очередь, но алгоритм поиска в ширину по-разному работает с ними, чтобы обеспечить объявленный порядок обхода. Если которая сначала содержит только <tex>(u, v) \in Es </tex> , и вершина множество посещенных вершин <tex>uX </tex> черного цвета, то вершина которое изначально тоже содержит только <tex>vs </tex> либо серая. На каждом шаге алгоритм вынимает из начала очереди вершину, либо черная, т.е. рассматривает все исходящие из нее ребра и добавляет все вершины, смежные связанные с ней уже открытынепосещенные вершины в <tex> X </tex> и в конец очереди. Серые вершины могут иметь белых соседейЕсли очередь пуста, представляя собой границу между открытыми и неоткрытыми вершинамито алгоритм завершает работу.

Поиск в ширину строит также может построить дерево поиска в ширину, которое изначально . Изначально оно состоит из одного корня<tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, которым является исходная то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex>s</tex> до <tex> t </tex> в <tex> G </tex>. Если в процессе сканирования списка смежности уже открытой  Также можно для каждой вершины <tex>ut \in V </tex> считать длину этого пути, равную <tex> d[t] </tex>. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до <tex> t </tex> равна <tex> \rho(s, t) </tex>, если <tex> t </tex> открывается белая вершина посещена и <tex>v\infty </tex>в противном случае. Отсюда следует, что если на каждом шаге обновлять длины путей, то информация о множестве <tex> X </tex> является избыточной, и его можно не хранить. == Анализ времени работы == Оценим время работы для входного графа <tex>G = (V, E)</tex>. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(V) </tex> операций. Для каждой вершины <tex>v</tex> и ребро рассматривается не более <tex> deg\ v </tex>(uребер, инцидентных ей. Так как <tex> \sum_{v\in V} deп\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(E)</tex> добавляются . Поэтому общее время работы алгоритма поиска в ширину — <tex> O(V + E) </tex>. === Корректность === {{Утверждение|statement=В алгоритме поиска в деревоширину очередь всегда содержит сначала вершины с расстоянием k, а потом, возможно, вершины с расстоянием k + 1.|proof=Докажем это утверждение индукцией по шагам алгоритма. База: изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием 0, утверждение верно.  Переход: пусть после <tex> l </tex>-ого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. При этом Тогда на <tex>ul+1 </tex> является '''предшественником''' -ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные(predecessor<tex> r </tex> вершин), или '''родителем''' связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex>(parentвозможно, 0)вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием k + 1, что соответствует нашему инварианту.}} {{Теорема|statement=Алгоритм поиска в ширину в невзвешенном графе находит оптимальные расстояния до всех достижимых вершин.|proof=Допустим, что это не так. Выберем из вершин, для которых найдено неоптимальное расстояние от <tex>vs </tex> ту, которая находится на минимальном расстоянии. Пусть это вершина <tex> u </tex> , и она имеет своим предком в дереве поиска обхода в ширину<tex> v </tex>, а предкок в оптимальном пути до <tex> v </tex> — вершина <tex> w </tex>. Расстояние до вершин <tex> v <tex> и <tex> w </tex> найдено корректно, путь через <tex> w </tex> оптимальный, а через <tex> v </tex> — нет, поэтому <tex> d[w] < d[v] </tex>. Поскольку Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть открыта предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, и найденные расстояния до всех вершин оптимальны.}} === Реализация === В приведенном ниже псевдокоде <tex> G = (V, E) </tex> - входной граф, <tex> s </tex> - выделенная вершина, Q - очередь. Множество <tex> X </tex> не более одного разахранится, вместо него использются расстояния в дереве обхода в ширину; расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, она имеет не более одного родителяхранится в поле <tex>d[u]</tex>.

1 '''for''' <tex>u \in V[G]</tex> 2 '''do''' <tex>color[u] \leftarrow</tex> WHITE 3 <tex>d[u] \leftarrow \mathcal {1}</tex> 4 <tex>p[us] \leftarrow</tex> NIL 5 <tex>color[s] \leftarrow</tex> GRAY 6 <tex>d[s] \leftarrow 0</tex> 7 <tex>p[s] \leftarrow</tex> NIL2 8 Q <tex>Q \leftarrow \varnothing</tex> 3 9 ENQUEUEQ.push(<tex>Q</tex>, <tex>s</tex>) 4 10 '''while''' Q <tex>Q \ne \varnothing</tex> 11 5 '''do''' u <tex>u \leftarrow</tex> DEQUEUE(<tex>Q</tex>).pop 12 6 '''for''' v: uv <tex>v \in Adj[u]</tex>E 13 7 '''do''' '''if''' <tex>colord[v] =<tex> \infty </tex> WHITE 14 8 '''then''' d[v] <tex>color[v] \leftarrow</tex> GRAY 15 <tex>d[v] \leftarrow d[u] + 1</tex> 16 <tex>p[v] \leftarrow u</tex> 17 ENQUEUE 9 Q.push(<tex>Q</tex>, <tex>v</tex>) 18 <tex>color[u] \leftarrow</tex>BLACK

== Анализ Литература ==Оценим время работы для входного графа <tex>G = (V, E)</tex>. После инициализации ни одна вершина не окрашивается в белый цвет, поэтому проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex>O(1)</tex> времени, так что общее время операций с очередью составляет <tex>O(V)</tex>. Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза. Так как сумма длин всех списков смежности равна <tex> \Theta (E) </tex>, общее время, необходимое для сканирования списков, равно <tex>O(E)</tex>. Накладные расходы на инициализацию равны <tex>O(V)</tex>, так что общее время работы процедуры '''BFS''' составляет <tex>O(V + E)</tex>. Таким образом, время работы поиска в ширину линейно зависит от размера представления графа <tex>G</tex> с использованием списков смежности.