Обход в ширину — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники информации)
(fixes)
Строка 3: Строка 3:
 
== Описание алгоритма ==
 
== Описание алгоритма ==
  
Пусть задан невзвешенный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Для алгоритма нам потребуются [[Очередь|очередь]], которая сначала содержит только <tex> s </tex>, и множество посещенных вершин <tex> X </tex>, которое изначально тоже содержит только <tex> s </tex>. На каждом шаге алгоритм вынимает из начала очереди вершину, рассматривает все исходящие из нее ребра и добавляет все связанные с ней непосещенные вершины в <tex> X </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работу.
+
Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.
  
Поиск в ширину также может построить дерево поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.
+
Для алгоритма нам потребуются [[Очередь|очередь]], которая сначала содержит только <tex> s </tex>, и множество посещенных вершин <tex> X </tex>, которое изначально тоже содержит только <tex> s </tex>. На каждом шаге алгоритм вынимает из начала очереди вершину, рассматривает все исходящие из нее ребра и добавляет все связанные с ней непосещенные вершины в <tex> X </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работу.
 +
 
 +
Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.
  
 
Также можно для каждой вершины <tex> t \in V </tex> считать длину этого пути, равную <tex> d[t] </tex>. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до <tex> t </tex> равна <tex> \rho(s, t) </tex>, если <tex> t </tex> посещена и <tex> \infty </tex> в противном случае. Отсюда следует, что если на каждом шаге обновлять длины путей, то информация о множестве <tex> X </tex> является избыточной, и его можно не хранить.
 
Также можно для каждой вершины <tex> t \in V </tex> считать длину этого пути, равную <tex> d[t] </tex>. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до <tex> t </tex> равна <tex> \rho(s, t) </tex>, если <tex> t </tex> посещена и <tex> \infty </tex> в противном случае. Отсюда следует, что если на каждом шаге обновлять длины путей, то информация о множестве <tex> X </tex> является избыточной, и его можно не хранить.
Строка 11: Строка 13:
 
== Анализ времени работы ==
 
== Анализ времени работы ==
  
Оценим время работы для входного графа <tex>G = (V, E)</tex>. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> deg\ v </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} deg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </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>.
  
 
== Корректность ==
 
== Корректность ==
Строка 21: Строка 23:
 
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.
 
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.
  
База: изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием 0, утверждение верно.  
+
'''База''': изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием <tex> 0 </tex>, утверждение верно.  
  
Переход: пусть после <tex> l </tex>-ого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. Тогда на <tex> l+1 </tex>-ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные(<tex> r </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex> (возможно, 0) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием k + 1, что соответствует нашему инварианту.
+
'''Переход''': пусть после <tex> l </tex>-ого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. Тогда на <tex> l+1 </tex>-ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные(<tex> r </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex> (возможно, <tex> 0 </tex>) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием <tex> k + 1 </tex>, что соответствует нашему инварианту.
 
}}
 
}}
  
Строка 41: Строка 43:
 
== Реализация ==
 
== Реализация ==
  
Предложенная ниже функция возвращает расстояние между вершинами source и destination. E - список ребер, Q - очередь. Множество <tex> X </tex> не хранится, вместо него используются расстояния в дереве обхода в ширину. Заметим, что расстояние от вершины source до вершины u, хранится в поле d[u].
+
Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
 +
<ul>
 +
    <li><tex> \mathtt{source} </tex> — исходная вершина</li>
 +
    <li><tex> \mathtt{destination} </tex> — конечная вершина</li>
 +
    <li><tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.</li>
 +
    <li><tex> \mathtt{Q} </tex> — очередь.</li>
 +
    <li>В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.</li>
 +
</ul>
  
  '''int''' '''BFS'''(E: '''list'''<'''int''', '''int'''>, source: '''int''', destination: '''int''')
+
  '''int''' '''BFS'''(E: <V, E>, source: '''int''', destination: '''int''')
 +
    d = int[|V|]
 
     d.fill(<tex> \infty </tex>)
 
     d.fill(<tex> \infty </tex>)
 
     d[source] = 0
 
     d[source] = 0
Строка 49: Строка 59:
 
     Q.push(source)
 
     Q.push(source)
 
     '''while''' Q <tex> \ne \varnothing </tex>  
 
     '''while''' Q <tex> \ne \varnothing </tex>  
         q = Q.pop()
+
         u = Q.pop()
         '''for''' <q, v> '''in''' E
+
         '''for''' vu '''in''' E
 
             '''if''' d[v] == <tex> \infty </tex>
 
             '''if''' d[v] == <tex> \infty </tex>
 
                 d[v] = d[q] + 1
 
                 d[v] = d[q] + 1
Строка 56: Строка 66:
 
     '''return''' d[destination]
 
     '''return''' d[destination]
  
== Примеры задач ==
+
Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
 +
 
 +
== Вариации алгоритма ==
 
=== 0-1 BFS ===
 
=== 0-1 BFS ===
Пусть в графе разрешены ребра веса 0 и 1, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом: вместо очереди будем использовать [[Персистентный_дек|дек]], а вместо добавления вершины в конец будем добавлять вершину в начало, если рассматриваемое ее ребро имеет вес 0, а иначе в конец. Соответственно релаксируем расстояние до вершины. Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.
+
Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1 </tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом: вместо очереди будем использовать [[Персистентный_дек|deque]] (steque), а вместо добавления вершины в конец будем добавлять вершину в начало, если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, а иначе в конец. Соответственно релаксируем расстояние до вершины. Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.
 
=== 1-k BFS ===
 
=== 1-k BFS ===
Пусть в графе разрешены ребра веса <tex>1..k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2..u_{m - 1}v</tex> (где <tex>u_1..u_{m - 1}</tex> - новые вершины). Применим данную операцию ко всем ребрам графа <tex>G(V, E)</tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Асимптотикой данного алгоритма является <tex> O(|V| + (2k - 1)|E|) </tex>.
+
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1..k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2..u_{m - 1}v</tex> (где <tex>u_1..u_{m - 1}</tex> - новые вершины). Применим данную операцию ко всем ребрам графа <tex>G(V, E)</tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Асимптотикой данного алгоритма является <tex> O(|V| + k|E|) </tex>.
  
 
== Источники информации ==
 
== Источники информации ==

Версия 18:56, 3 декабря 2014

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

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

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

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

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

Также можно для каждой вершины [math] t \in V [/math] считать длину этого пути, равную [math] d[t] [/math]. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до [math] t [/math] равна [math] \rho(s, t) [/math], если [math] t [/math] посещена и [math] \infty [/math] в противном случае. Отсюда следует, что если на каждом шаге обновлять длины путей, то информация о множестве [math] X [/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] 0 [/math], утверждение верно.

Переход: пусть после [math] l [/math]-ого шага алгоритма очередь содержит [math] p [/math] вершин с расстоянием [math] k [/math] и [math] q [/math] вершин с расстоянием [math] k + 1 [/math]. Тогда на [math] l+1 [/math]-ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные([math] r [/math] вершин), связанные с ней; расстояние до них, очевидно, будет равно [math] k + 1 [/math]. У нас останется [math] p - 1 [/math] (возможно, [math] 0 [/math]) вершин с расстоянием [math] k [/math] и [math] q + r [/math] вершин с расстоянием [math] k + 1 [/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] \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(E: <V, E>, source: int, destination: int)
    d = int[|V|]
    d.fill([math] \infty [/math])
    d[source] = 0
    Q = [math] \varnothing [/math]
    Q.push(source)
    while Q [math] \ne \varnothing [/math] 
        u = Q.pop()
        for vu in E
            if d[v] == [math] \infty [/math]
                d[v] = d[q] + 1
                Q.push(v)
    return d[destination]

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

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

0-1 BFS

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

1-k BFS

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

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