Обход в ширину — различия между версиями
Sementry (обсуждение | вклад) м (some minor fixes) |
Sementry (обсуждение | вклад) м (убрал все вхождения слова "оптимальный" в текст статьи) |
||
Строка 33: | Строка 33: | ||
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин. | Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин. | ||
|proof= | |proof= | ||
− | Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, длина найденного расстояния до которой минимальна. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в | + | Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, длина найденного расстояния до которой минимальна. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>. Расстояние до вершин <tex> v </tex> и <tex> w </tex> найдено корректно(по выбору вершины <tex> u </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> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими. |
}} | }} | ||
Версия 05:32, 17 ноября 2011
Эта статья находится в разработке!
Обход в ширину (Поиск в ширину, BFS, Breadth-first search) — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.
Содержание
Алгоритм
Общая идея
Пусть задан невзвешенный граф
, в котором выделена исходная вершина . Для алгоритма нам потребуются очередь, которая сначала содержит только , и множество посещенных вершин , которое изначально тоже содержит только . На каждом шаге алгоритм вынимает из начала очереди вершину, рассматривает все исходящие из нее ребра и добавляет все связанные с ней непосещенные вершины в и в конец очереди. Если очередь пуста, то алгоритм завершает работу.Поиск в ширину также может построить дерево поиска в ширину. Изначально оно состоит из одного корня
. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из вершины путь в дереве поиска в ширину соответствует кратчайшему пути от до в .Также можно для каждой вершины
считать длину этого пути, равную . Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до равна , если посещена и в противном случае. Отсюда следует, что если на каждом шаге обновлять длины путей, то информация о множестве является избыточной, и его можно не хранить.Анализ времени работы
Оценим время работы для входного графа
. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют времени, так что общее время работы с очередью составляет операций. Для каждой вершины рассматривается не более ребер, инцидентных ей. Так как , то время, используемое на работу с ребрами, составляет . Поэтому общее время работы алгоритма поиска в ширину — .Корректность
Утверждение: |
В алгоритме поиска в ширину очередь всегда содержит сначала некоторое количество вершин с расстоянием k, а потом некоторое количество вершин с расстоянием k + 1(возможно, нулевое). |
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов. База: изначально очередь содержит только одну вершину Переход: пусть после с расстоянием 0, утверждение верно. -ого шага алгоритма очередь содержит вершин с расстоянием и вершин с расстоянием . Тогда на -ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные( вершин), связанные с ней; расстояние до них, очевидно, будет равно . У нас останется (возможно, 0) вершин с расстоянием и вершин с расстоянием k + 1, что соответствует нашему инварианту. |
Теорема: |
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин. |
Доказательство: |
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от | найдены некорректно, ту, длина найденного расстояния до которой минимальна. Пусть это вершина , и она имеет своим предком в дереве обхода в ширину , а предок в кратчайшем пути до — вершина . Расстояние до вершин и найдено корректно(по выбору вершины ). Путь через кратчайший, а через — нет, поэтому . Из ранее доказанной леммы следует, что в этом случае вершина попала в очередь и была обработана раньше, чем . Но она соединена с , значит, не может быть предком в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
Реализация
В приведенном ниже псевдокоде
- входной граф, - выделенная вершина, Q - очередь. Множество не хранится, вместо него использются расстояния в дереве обхода в ширину; расстояние от до вершины , вычисляемое алгоритмом, хранится в поле .BFS(, ) 1 d[s] 0 2 Q 3 Q.push(s) 4 while Q 5 do u Q.pop 6 for v: uv E 7 do if d[v] = 8 then d[v] d[u] + 1 9 Q.push(v)
Ссылки
Литература
- Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1