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

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

Описание алгоритма

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

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

Анализ времени работы

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

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

Утверждение:

В очереди поиска в ширину расстояние вершин до [math]s[/math] монотонно неубывает.

[math]\triangleright[/math]

Докажем это утверждение индукцией по числу выполненных алгоритмом шагов. Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до [math] s [/math] отличается не более чем на [math] 1 [/math]. База: изначально очередь содержит только одну вершину [math] s [/math]. Переход: пусть после [math] i-й [/math] итерации в очереди [math] a + 1 [/math] вершин с расстоянием [math] x [/math] и [math] b [/math] вершин с расстоянием [math] x + 1 [/math]. Рассмотрим [math] i-ю [/math] итерацию. Из очереди достаем вершину [math] v [/math], с расстоянием [math] x [/math]. Пусть у v есть [math]r [/math] непосещенных смежных вершин. Тогда, после их добавления, в очереди находится [math] a [/math] вершин с расстоянием [math] x [/math] и, после них, [math] b + r [/math] вершин с расстоянием [math] x + 1 [/math]. Оба инварианта сохранились, [math] \Rightarrow [/math] после любого шага алгоритма элементы в очереди неубывают.

[math]\triangleleft[/math]

Теорема:

Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.

Доказательство:

[math]\triangleright[/math]

Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от [math] s [/math] найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина [math] u [/math], и она имеет своим предком в дереве обхода в ширину [math] v [/math], а предок в кратчайшем пути до [math] u [/math] — вершина [math] w [/math]. Так как [math] w [/math] — предок [math] u [/math] в кратчайшем пути, то [math] \rho(s, u) = \rho(s, w) + 1 \gt \rho(s, w) [/math], и расстояние до w найдено верно, [math] \rho(s, w) = d[w] [/math]. Значит, [math] \rho(s, u) = d[w] + 1 [/math]. Так как [math] v [/math] — предок [math] u [/math] в дереве обхода в ширину, то [math] d[u] = d[v] + 1 [/math]. Расстояние до [math] u [/math] найдено некорректно, поэтому [math] \rho(s, u) \lt d[u] [/math]. Подставляя сюда два последних равенства, получаем [math] d[w] + 1 \lt d[v] + 1 [/math], то есть, [math] d[w] \lt d[v] [/math]. Из ранее доказанной леммы следует, что в этом случае вершина [math] w [/math] попала в очередь и была обработана раньше, чем [math] v [/math]. Но она соединена с [math] u [/math], значит, [math] v [/math] не может быть предком [math] u [/math] в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.

[math]\triangleleft[/math]

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

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

Реализация

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.

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

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

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

Вариации алгоритма

0-1 BFS

Пусть в графе разрешены ребра веса [math] 0 [/math] и [math] 1 [/math], необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом:

Вместо очереди будем использовать дек (или можно даже steque). Если рассматриваемое ее ребро имеет вес [math] 0 [/math], то будем добавлять вершину в начало, а иначе в конец. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

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

1-k BFS

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

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

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
• MAXimal :: algo :: Поиск в ширину
• Wikipedia — Breadth-first search
• Wikipedia — Поиск в ширину
• Визуализатор алгоритма