Обход в ширину
Обход в ширину (Поиск в ширину, англ. BFS, Breadth-first search) — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.
Описание алгоритма
Алгоритм BFS
посещенные вершины
Пусть задан невзвешенный ориентированный граф [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(v) [/math] ребер, инцидентных ей. Так как [math] \sum\limits_ \mathrm(v) = 2|E| [/math] , то время, используемое на работу с ребрами, составляет [math] O(|E|) [/math] . Поэтому общее время работы алгоритма поиска в ширину — [math] O(|V| + |E|) [/math] .
Корректность
В очереди поиска в ширину расстояние вершин до [math]s[/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] . Пусть у [math]v[/math] есть [math]r [/math] непосещенных смежных вершин. Тогда, после их добавления, в очереди находится [math] a [/math] вершин с расстоянием [math] x [/math] и, после них, [math] b + r [/math] вершин с расстоянием [math] x + 1 [/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] , и расстояние до [math] w [/math] найдено верно, [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] s [/math] . Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из [math] s [/math] вершины [math] t [/math] путь в дереве поиска в ширину соответствует кратчайшему пути от [math] s [/math] до [math] t [/math] в [math] G [/math] .
Реализация
Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
- [math] \mathtt [/math] — исходная вершина
- [math] \mathtt [/math] — конечная вершина
- [math] \mathtt [/math] — граф, состоящий из списка вершин [math] \mathtt [/math] и списка смежности [math] \mathtt [/math] . Вершины нумеруются целыми числами.
- [math] \mathtt [/math] — очередь.
- В поле [math] \mathtt [/math] хранится расстояние от [math] \mathtt [/math] до [math] \mathtt [/math] .
int BFS(G: (V, E), source: int, destination: int): d = int[|V|] fill(d,) d[source] = 0 Q = Q.push(source) while Q u = Q.pop() for v: (u, v) in E if d[v] == d[v] = d[u] + 1 Q.push(v) return d[destination]
Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение [math] \mathtt [/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_v[/math] (где [math]u_1 \ldots u_[/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 — Поиск в ширину
- Визуализатор алгоритма
- Алгоритмы и структуры данных
- Кратчайшие пути в графах
Что такое bfs
BFS, или Breadth First Search — алгоритм обхода графа в ширину. Граф — это структура из «вершин» и «ребер», соединяющих между собой вершины. По ребрам можно передвигаться от одной вершине к другой, и BFS делает это поуровнево: сначала проходит по всем ближайшим от начальной точки вершинам, потом спускается глубже.
Освойте профессию «Data Scientist»
Выглядит это так: алгоритм начинает в заранее выбранной вершине и сначала «посещает» и отмечает всех соседей этой вершины. Потом он переходит к соседям посещенных вершин, затем — дальше по тому же принципу. Из-за характера распространения, похожего на волну, алгоритм еще называют волновым. BFS — один из двух популярных алгоритмов обхода. Второй называется DFS и подразумевает обход в глубину: сначала алгоритм проходит по ребрам «вглубь» графа.
Профессия / 24 месяца
Data Scientist
Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.
Кто пользуется BFS
- Дата-сайентисты, которые работают с информацией и ее распространением, часто взаимодействуют с теорией графов.
- Разработчики, имеющие дело с определенными видами задач: поиск оптимального маршрута, программирование передвижения «умных» машин, разработка интеллектуальных систем и другие.
- Математики и другие ученые, которые работают с теорией графов как с фундаментальным научным знанием или в контексте решения практических задач.
- Инженеры-электроники: конкретно алгоритм BFS используется при трассировке печатных плат.
- Технические специалисты, работающие в телекоммуникационных системах. Там тоже активно применяется теория графов и в частности BFS.
- Сетевые инженеры, так как теория графов активно используется в сетевых технологиях. BFS, например, применяют при обходе P2P-сетей, или пиринговых сетей, а на них основаны многие сетевые протоколы. В частности, пиринговую сеть реализует BitTorrent.
Станьте дата-сайентистом и решайте амбициозные задачи с помощью нейросетей
Для чего нужен BFS
- Для решения задач поиска оптимального пути. Классической задачей считается автоматизированный поиск выхода из лабиринта.
- Для решения задач, связанных непосредственно с теорией графов, например для поиска компонент связности. Эти задачи в свою очередь решаются в Data Science, теории сетей и электронике.
- Для задач искусственного интеллекта, связанных с поиском решения с минимальным количеством ходов. В таком случае состояния «умной машины» представляются как вершины, а переходы между ними — как ребра.
- Для оптимизации памяти при обходе графа в некоторых ситуациях, например для некоторых специфических структур.
- Для работы с информацией в определенных структурах данных, таких как деревья. Их тоже можно обходить с помощью алгоритма BFS, потому что они — подвид графов.
Особенности BFS
- Константное количество действий для каждого ребра или вершины. Это важно при расчете сложности алгоритма — при выборе оптимального метода решения той или иной задачи.
- Отсутствие проблемы «бесконечного цикла»: алгоритм не попадет в него ни при каких условиях благодаря особенностям работы.
- Высокая точность и надежная архитектура, которая позволяет полагаться на этот алгоритм в решении различных задач.
- Возможность работать и с ориентированными, и с неориентированными графами. О том, чем они различаются, можно прочитать в статье про ориентированный граф.
- Полнота алгоритма — он найдет решение, то есть кратчайший путь, и завершится на любом конечном графе. Если граф бесконечный, решение найдется только в том случае, если конечен какой-либо из его путей.
- Возможность находить кратчайший путь в графе, если все ребра одинаковой длины. Если длины ребер разные, BFS найдет путь с минимальным количеством ребер, но он не обязательно будет самым коротким. Для поиска кратчайшего пути в таком случае будет лучше алгоритм Дейкстры.
Как работает алгоритм BFS
Алгоритм простой и интуитивно понятный. Он проходит по вершинам графа, пока в том не останется непосещенных вершин, и рассчитывает самый короткий путь до целевой вершины. Чтобы показать его работу нагляднее, представим алгоритм пошагово.
Начало работы. В качестве начальной можно выбрать любую вершину. На момент начала работы алгоритма все вершины помечены как непосещенные — их называют «белыми». Первое, что делает алгоритм, — помечает начальную вершину как посещенную (также используют термины «развернутая» или «серая»). Если она и есть целевая, на этом алгоритм завершается. Но чаще всего это не так.
Поиск соседей. Алгоритм проверяет, какие соседи есть у начальной вершины. Они добавляются в «очередь действий» в том порядке, в каком алгоритм их нашел, и тоже помечаются как «серые». Это продолжается, пока у начальной вершины не останется «белых» соседей.
Переход на следующую вершину. Когда алгоритм проходит по всем соседям начальной вершины, он помечает ее как полностью обойденную. Такие вершины еще называют «черными»: алгоритм к ним не возвращается. Затем он переходит к одной из «серых» вершин — соседей начальной. Алгоритм выбирает первую вершину в очереди. Далее действия повторяются: «соседи» вершины, кроме «черной», заносятся в очередь.
Когда и эта вершина будет пройдена, переход повторится по тому же принципу — первая вершина в очереди. В этом случае ею будет второй сосед начальной вершины — мы помним, что их добавляли в очередь первыми. И только когда соседи начальной вершины в очереди закончатся, алгоритм пойдет по следующему «уровню» вершин. Так и достигается обход в ширину.
Конец алгоритма. Если очередь оказалась пустой, это значит, что «белых» и «серых» вершин больше не осталось. Алгоритм завершится. Если при этом целевая вершина не будет достигнута, это значит, что доступа к ней из начальной точки нет.
Если целевая вершина достигается раньше, чем алгоритм пройдет по всему графу, это также может означать его завершение. Алгоритм остановится, потому что задача окажется выполнена: самый короткий путь к целевой вершине будет найден.
Как реализовать алгоритм BFS
Реализация алгоритма возможна на любом языке программирования, который вы знаете. Граф обычно представляется как массив, очередь или другая структура данных. Ее элементы — вершины, и в них хранятся сведения о других вершинах, с которыми они соединены. Иногда там напрямую есть ссылки на другие вершины — конкретная реализация зависит от языка программирования и выбранной архитектуры.
Алгоритм BFS, реализованный программно, начинает с заданного элемента этой структуры данных — это аналогично начальной вершине. Он отмечает ее посещенной, или «серой» — например, записывает в элемент какое-то значение-метку. Затем он смотрит, на какие элементы ссылается начальный, и отмечает посещенными уже их. Когда все ссылки на другие элементы в начальной вершине заканчиваются, граф помечает ее как полностью обойденную, «черную» — для этого используется другое значение-метка. Оно показывает алгоритму, что больше возвращаться в эту вершину нет смысла, — так он не «застрянет» в одних и тех же точках.
После этого алгоритм переходит по ссылке к первому найденному «соседу» этой вершины и повторяет те же действия. Это продолжается, пока все вершины не окажутся помеченными как полностью обойденные.
Вы можете подробнее познакомиться с теорией графов, ее задачами, методами их решения и программными реализациями этих методов на курсах SkillFactory.
Data Scientist
Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.
Статьи по теме:
Обход графа в ширину (BFS) и глубину (DFS)
Задумка данного поста заключается в том, чтобы коротко и ясно объяснить как работают на графах данные алгоритмы. То есть целью поста в первую очередь является понимание, а не детали реализации в коде.
Зачем нужны данные алгоритмы?
Обход в ширину и обход в глубину — два алгоритма, являющиеся основой для большинства сложных алгоритмов, имеющих реальное применение в жизни. Не задумываясь, мы сталкиваемся с графами постоянно. Как самый банальный пример — навигатор. Построение маршрута — уже задача, в которой используются данные алгоритмы.
Обход в глубину (Depth-First Search, DFS)
Один из основных методов обхода графа, часто используемый для проверки связности графа, поиска цикла и компонент сильной связности и для топологической сортировки. Отбросим все эти сложные слова до поры до времени, а пока посмотрим, что же делает DFS и как он это делает. Будем рассматривать реализацию на списке смежности как самую легкую для понимания. Вкратце напомню, что список смежности — это один из способов представления графа, который выглядит примерно так:
Для каждой вершины (первый столбик) мы составляем список смежных ей вершин, то есть список вершин с которыми у данной есть общие ребра(ребро инцидентное данным вершинам).
Теперь собственно к самому алгоритму, принцип его работы совпадает с его названием, данный алгоритм идет «внутрь» графа, до того момента как ему становится некуда идти, затем возвращается в предыдущую вершину и снова идет от нее до тех пор, пока есть куда идти. И так далее. Для понимания данного алгоритма нам потребуются 3 цвета, один будет обозначать, что вершину мы еще не посетили, второй что посетили и ушли, а третий, что посетили и не смогли идти дальше и начинаем возвращаться обратно.
Стартуем из любой вершины, например, из первой. Идем по списку смежности. Из 1 вершины попадаем во вторую, переходим в ее список смежности, не забываем красить 1 вершину в серый, так как мы ее посетили и ушли дальше. Из второй вершины идем в любую из списка смежности второй вершины, например в 3. Красим 2 в серый и идем в список смежности 3-й вершины. А в нем ничего нет. В таком случае мы понимаем, что дальше нам идти не куда, пора возвращаться.
Красим 3 в черный так как нам идти некуда(нет белых вершин, в которые мы могли бы пойти из 3). Возвращаемся в 2 и в ее список смежности, видим что там еще есть вершина 4, выдвигаемся туда, оттуда можно пойти только в 1, но она уже серая, то есть мы там уже были. Алгоритм начнет рекурсивно откатываться назад перекрашивая все вершины в черный, думаю принцип уже понятен.
Псевдокод
Что здесь происходит? Все то, что мы уже видели, только в коде. G.Adj — список смежности данного графа. Для каждой вершины если она еще не посещена — красим ее в серый, то есть в true ее поле visited, таким образом пройдемся по всем вершинам. Зачем мы в init() вызываем dfs для каждой вершины? Мы можем не угадать с первой вершиной, как например в графе сверху, если бы мы начали с вершины 3, дфс бы закончился сразу, так как из нее нет исходящих дуг.
Обход в ширину (breadth-first search, BFS)
Систематически обходит все вершины графа. В чем его отличие от обхода в глубину? Обход в глубину «перепрыгивает» между строками списка смежности по 1 вершине за раз, а обход в ширину сразу по всем возможным, посмотрим как он работает на примере:
Сначала мы проходимся по всем вершинам смежным со стартовой, потом по всем, смежным со смежными стартовой и так далее. Вот еще один пример, который как мне кажется более наглядно показывает различие обходов в глубину и ширину: в 1-м граф как бы обходится равномерно.
Псевдокод с краткими пояснениями:
Заключение
Два этих алгоритма очень важны для понимания. Искренне надеюсь, что данный пост дал читателю хотя бы примерное представление о том, как работают обходы в глубину и ширину, так как полное понимание вы получите только после применения этих алгоритмов на практике.
Поиск в ширину
Поиск в ширину (англ. breadth-first search) — один из основных алгоритмов на графах, позволяющий находить все кратчайшие пути от заданной вершины и решать многие другие задачи.
Поиск в ширину также называют обходом — так же, как поиск в глубину и все другие обходы, он посещает все вершины графа по одному разу, только в другом порядке: по увеличению расстояния до начальной вершины.
#Описание алгоритма
На вход алгоритма подаётся невзвешенный граф и номер стартовой вершины $s$. Граф может быть как ориентированным, так и неориентированным — для алгоритма это не важно.
Основную идею алгоритма можно понимать как процесс «поджигания» графа: на нулевом шаге мы поджигаем вершину $s$, а на каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей, в конечном счете поджигая весь граф.
Если моделировать этот процесс, то за каждую итерацию алгоритма будет происходить расширение «кольца огня» в ширину на единицу. Номер шага, на котором вершина $v$ начинает гореть, в точности равен длине её минимального пути из вершины $s$.