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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Отмена правки 13299 участника Sementry (обсуждение)(или не бред?))
м (кажется, теперь все правильно)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
'''Обход в ширину''' ('''Поиск в ширину, BFS''', '''Breadth-first search''') — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.
+
'''Обход в ширину''' ('''Поиск в ширину''', '''BFS''', '''Breadth-first search''') — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.
  
 
== Алгоритм ==
 
== Алгоритм ==
Строка 14: Строка 14:
 
=== Анализ времени работы ===
 
=== Анализ времени работы ===
  
Оценим время работы для входного графа <tex>G = (V, E)</tex>. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> deg\ v </tex> ребер, инцидентных ей. Так как <tex> \sum_{v \in V} deg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.
+
Оценим время работы для входного графа <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>.
  
 
=== Корректность ===
 
=== Корректность ===
Строка 26: Строка 26:
 
База: изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием 0, утверждение верно.  
 
База: изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием 0, утверждение верно.  
  
Переход: пусть после <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> (возможно, 0) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием k + 1, что соответствует нашему инварианту.
 
}}
 
}}
  
Строка 33: Строка 33:
 
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
 
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
 
|proof=
 
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, длина найденного расстояния до которой минимальна. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.
+
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.
  
Пусть <tex> s{w_1}{w_2}{\ldots}wu </tex> - этот кратчайший путь. Понятно, что <tex> s{w_1}{w_2}{\ldots}w </tex> - кратчайший путь до <tex> w </tex> (если бы он не был кратчайшим, то можно было бы заменить его на кратчайший в пути до <tex> u </tex>, значит, путь до <tex> u </tex> — тоже не кратчайший). Вес каждого ребра равен 1, значит, <tex> d[u] > \rho(s, u) = d[w] + 1 </tex>, и <tex> d[w] < d[u] </tex>. Неравенство <tex> d[v] < d[u] </tex> следует из того, что <tex> v </tex> — предок <tex> u </tex> в дереве поиска в ширину. Итак, расстояние до вершин <tex> v </tex> и <tex> w </tex> найдено корректно.
+
Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до w найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </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> 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> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
 
}}
 
}}
  

Версия 07:37, 21 ноября 2011

Эта статья находится в разработке!

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

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

Утверждение:
В алгоритме поиска в ширину очередь всегда содержит сначала некоторое количество вершин с расстоянием k, а потом некоторое количество вершин с расстоянием k + 1(возможно, нулевое).
[math]\triangleright[/math]

Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

База: изначально очередь содержит только одну вершину [math] s [/math] с расстоянием 0, утверждение верно.

Переход: пусть после [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] (возможно, 0) вершин с расстоянием [math] k [/math] и [math] q + r [/math] вершин с расстоянием k + 1, что соответствует нашему инварианту.
[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] G = (V, E) [/math] - входной граф, [math] s [/math] - выделенная вершина, Q - очередь. Множество [math] X [/math] не хранится, вместо него использются расстояния в дереве обхода в ширину; расстояние от [math]s[/math] до вершины [math]u[/math], вычисляемое алгоритмом, хранится в поле [math]d[u][/math].

BFS([math]G[/math], [math]s[/math])
1    d[s] [math] \leftarrow [/math] 0
2    Q [math] \leftarrow \emptyset [/math]
3    Q.push(s)
4    while Q [math] \ne \emptyset [/math] 
5      do u [math] \leftarrow [/math] Q.pop
6        for v: uv [math] \in [/math] E
7          do if d[v] = [math] \infty [/math]
8            then d[v] [math] \leftarrow [/math] d[u] + 1
9                 Q.push(v)

Ссылки

Поиск в ширину на e-maxx.ru

Поиск в ширину в Википедии

Визуализатор алгоритма

Литература

  • Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1