Что такое bfs

Графы для самых маленьких: BFS

Требуется найти путь от одной вершины графа до другой, причем путь должен быть минимальным по количеству ребер.

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

• Полностью обработанные вершины (изначально множество пусто, на рисунке обозначено черным цветом)
• Вершины, до которых известно расстояние (изначально в множестве только одна вершина — начальная, на рисунке обозначено серым цветом)
• Вершины, про которые ничего не известно (изначально — все вершины, кроме начальной, на рисунке обозначено белым цветом)

1. w — черная или серая вершина. В таком случае, мы не получаем никакой новой информации.
2. w — белая вершина. Тогда расстояние до нее равно d(w) = d(v) + 1. И, поскольку мы узнали расстояние, w становится серой вершиной

Реализация

Почему это работает?

1. d[v] ≤ k
   • База: вершина p[0] = start посещается алгоритмом, причем d[p[0]] = 0
   • Предположение: вершина p[i — 1] посещается алгоритмом, причем d[p[i]] ≤ i
   • Шаг: при рассмотрении вершины p[i — 1] (а может, и раньше) будет рассмотрено ребро, ведущее в вершину p[i]. Таким образом, d[p[i]] ≤ i
2. d[v] ≥ k
   Предположим, что d[v] < k. Рассмотрим вершину v; ту вершину, при рассмотрении которой вершина v была покрашена в серый цвет (обозначим ее w); ту вершину, при рассмотрении которой вершина w была покрашена в серый цвет;…; начальную вершину start. Каждые две соседние вершины в этой последовательности соединены ребром по построению алгоритма. Таким образом, мы нашли путь из вершины start до вершины v длиной менее k — противоречие, следовательно, d[v] ≥ k

Сложность алгоритма

Для каждого ребра и каждой вершины алгоритм выполняет константное число действий, следовательно, временная сложность — O(V + E).
Максимальное число вершин, одновременно хранящихся в очереди — V, то есть, максимальный объем используемой памяти — O(V).

Поиск в ширину

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

Поиск в ширину также называют обходом — так же, как поиск в глубину и все другие обходы, он посещает все вершины графа по одному разу, только в другом порядке: по увеличению расстояния до начальной вершины.

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

На вход алгоритма подаётся невзвешенный граф и номер стартовой вершины $s$. Граф может быть как ориентированным, так и неориентированным — для алгоритма это не важно.

Основную идею алгоритма можно понимать как процесс «поджигания» графа: на нулевом шаге мы поджигаем вершину $s$, а на каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей, в конечном счете поджигая весь граф.

Если моделировать этот процесс, то за каждую итерацию алгоритма будет происходить расширение «кольца огня» в ширину на единицу. Номер шага, на котором вершина $v$ начинает гореть, в точности равен длине её минимального пути из вершины $s$.

Моделировать это можно следующим образом. Создадим очередь, в которую будут помещаться горящие вершины, а также заведём булевый массив, в котором для каждой вершины будем отмечать, горит она или нет — или иными словами, была ли она уже посещена. Изначально в очередь помещается только вершина $s$, которая сразу помечается горящей.

Затем алгоритм представляет собой такой цикл: пока очередь не пуста, достать из её головы одну вершину $v$, просмотреть все рёбра, исходящие из этой вершины, и если какие-то из смежных вершин $u$ ещё не горят, поджечь их и поместить в конец очереди.

В итоге, когда очередь опустеет, мы по одному разу обойдём все достижимые из $s$ вершины, причём до каждой дойдём кратчайшим путём. Длины кратчайших путей можно посчитать, если завести для них отдельный массив $d$ и при добавлении в очередь пересчитывать по правилу $d_u = d_v + 1$. Также можно компактно сохранить дополнительную информацию для восстановления самих путей, заведя массив «предков», в котором для каждой вершины хранится номер вершины из которой мы в неё попали.

#Реализация

Если мы всё равно поддерживаем массив расстояний, то отдельный булевый массив с метками горящих вершин можно не создавать, а вместо этого просто присвоить изначальное расстояние всех вершин некоторым некоторым специальным значением (например, -1), которое будет сигнализировать а том, что эту вершину мы ещё не просмотрели.

Теперь, чтобы восстановить кратчайший путь до какой-то вершины $v$, это можно сделать через массив p :

Обратим внимание, что путь выведется в обратном порядке.

#В неявных графах

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

В качестве конкретного примера, пусть у нас есть булева матрица размера $n \times n$, в которой помечено, свободна ли клетка с координатами $(x, y)$, и требуется найти кратчайший путь от $(x_s, y_t)$ до $(x_y, y_t)$ при условии, что за один шаг можно перемещаться в свободную соседнюю по вертикали или горизонтали клетку.

Поиск в ширину можно использовать для нахождения выхода из лабиринта

Можно сконвертировать граф в явный формат: как-нибудь пронумеровать все ячейки (например по формуле $x \cdot n + y$) и для каждой посмотреть на всех её соседей, добавляя ребро в $(x \pm 1, y \pm 1)$, если соответствующая клетка свободна.

Такой подход будет работать за оптимальное линейное время, однако с точки зрения реализации проще адаптировать не входные данные, а сам алгоритм обхода в глубину:

Перед запуском bfs следует убедиться, что не произойдет выход за пределы границ. Вместо того, чтобы добавлять проверки на _x < 0 || x >= n и т. п. при просмотре возможных соседей, удобно сделать следующий трюк: изначально создать матрицу a с размерностями на 2 больше, чем нужно, и на этапе чтения данных заполнять её в индексации не с нуля, а с единицы. Тогда границы матрицы всегда будут заполнены нулями (то есть помечены непроходимыми) и алгоритм никогда в них не зайдет.

#Применения и обобщения

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

Множественный BFS. Добавив в очередь изначально не одну, а несколько вершин, мы найдем для каждой вершины кратчайшее расстояние до одной из них.

Это полезно для задач, в которых нужно моделировать пожар, наводнение, извержение вулкана или подобные явления, в которых источник «волны» не один. Также так можно чуть быстрее находить кратчайший путь для конкретной пары вершин, запустив параллельно два обхода от каждой и остановив в тот момент, когда они встретятся.

Игры. С помощью BFS можно найти решение какой-либо задачи / игры за наименьшее число ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа.

В качестве (нетривиального) примера: собрать кубик Рубика за наименьшее число ходов.

Кратчайшие циклы. Чтобы найти кратчайший цикл в ориентированном невзвешенном графе, можно произвести поиск в ширину из каждой вершины. Как только в процессе обхода мы пытаемся пойти из текущей вершины по какому-то ребру в уже посещённую вершину, то это означает, что мы нашли кратчайший цикл для данной вершины, и останавливаем обход. Среди всех таких найденных циклов (по одному от каждого запуска обхода) выбираем кратчайший.

Такой алгоритм будет работать за $O(n^2)$: худшим случаем будет один большой цикл, в котором мы для каждой вершины пройдемся по всем остальным.

Ребра на кратчайшем пути. Мы можем за линейное время найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин $a$ и $b$. Для этого нужно запустить два поиска в ширину: из $a$ и из $b$.

Обозначим через $d_a$ и $d_b$ массивы кратчайших расстояний, получившиеся в результате этих обходов. Тогда каждое ребро $(u,v)$ можно проверить критерием

$$ d_a[u] + d_b[v] + 1 = d_a[b] $$

Альтернативно, можно запустить один обход из $a$, и когда он дойдет до $b$, начать рекурсивно проходиться по всем обратным ребрам, ведущим в более близкие к $a$ вершины (то есть те, для которых $d[u] = d[v] — 1$), отдельно помечая их.

Аналогично можно найти все вершины на каком-либо кратчайшем пути.

0-1 BFS. Если веса некоторых ребер могут быть нулевыми, то кратчайшие пути искать не сильно сложнее.

Ключевое наблюдение: если от вершины $a$ до вершины $b$ можно дойти по пути, состоящему из нулевых рёбер, то кратчайшие расстояния от вершины $s$ до этих вершин совпадают.

Если в нашем графе оставить только $0$-рёбра, то он распадётся на компоненты связности, в каждой из которых ответ одинаковый. Если теперь вернуть единичные рёбра и сказать, что эти рёбра соединяют не вершины, а компоненты связности, то мы сведём задачу к обычному BFS.

Получается, запустив обход, мы можем при обработке вершины $v$, у которой есть нулевые ребра в непосещенные вершины, сразу пройтись по ним и добавить все вершины нулевой компоненты, проставив им такое же расстояние, как и у $v$.

Это можно сделать и напрямую, запустив BFS внутри BFS, однако можно заметить, что достаточно при посещении вершины просто добавлять всех её непосещенных соседей по нулевым ребрам в голову очереди, чтобы обработать их раньше, чем те, которые там уже есть. Это легко сделать, если очередь заменить деком:

Также вместо дека можно завести две очереди: одну для нулевых ребер, а другую для единичных, в внутри цикла while сначала просматривать первую, а только потом, когда она станет пустой, вторую. Этот подход уже можно обобщить.

1-k BFS. Теперь веса рёбер принимают значения от $1$ до некоторого небольшого $k$, и всё так же требуется найти кратчайшие расстояния от вершины $s$, но уже в плане суммарного веса.

Наблюдение: максимальное кратчайшее расстояние в графе равно $(n — 1) \cdot k$.

Заведём для каждого расстояния $d$ очередь $q_d$, в которой будут храниться вершины, находящиеся на расстоянии $d$ от $s$ — плюс, возможно, некоторые вершины, до которых мы уже нашли путь длины $d$ от $s$, но для которых возможно существует более короткий путь. Нам потребуется $O((n — 1) \cdot k)$ очередей.

Положим изначально вершину $s$ в $q_0$, а дальше будем брать вершину из наименьшего непустого списка и класть всех её непосещенных соседей в очередь с номером $d_v + w$ и релаксировать $d_u$, не забывая при этом, что кратчайшее расстояние до неё на самом деле может быть и меньше.

Сложность такого алгоритма будет $O(k n + m)$, поскольку каждую вершину мы можем прорелаксировать и добавить в другую очередь не более $k$ раз, а просматривать рёбра, исходящие из вершины мы будем только когда обработаем эту вершину в самый первый раз.

На самом деле, нам так много списков не нужно. Если каждое ребро имеет вес не более $k$, то в любой момент времени не более $k$ очередей будут непустыми. Мы можем завести только $k$ списков, и вместо добавления в $(d_v + w)$-ый список использовать $(d_v+w) \bmod k$.

Заметим, что алгоритм также работает когда есть общее ограничение на длину пути, а не только на вес каждого ребра. Для более общего случая, когда веса ребер могут быть любыми неотрицательными, есть алгоритм Дейкстры, который мы разберем в следующей статье.

Поиск в ширину (BFS)

Поиск в ширину (англ. breadth-first search, BFS) — метод обхода и поиска пути в графе. Когда мы говорим слово “обход” мы подразумеваем, что мы посещаем вершины графа в определенном порядке. Одним из часто используемых методов обхода графа является обход в ширину (BFS). Суть BFS достаточно проста. Обход начинается с посещения определённой вершины (для обхода всего графа часто выбирается произвольная вершина). Затем алгоритм посещает соседей этой вершины. За ними — соседей соседей, и так далее.

Ниже представлена визуализация алгоритма BFS. Серым помечены вершины в очереди на посещение, чёрным — уже посещённые.

Реализация

Для реализации алгоритма нам потребуется очередь из вершин для посещения. При посещении очередной вершины в очередь добавляются все её соседи, которые ещё не были посещены. Для проверки, была ли вершина уже посещена, используется массив меток. Изначально \(visited[i] = false\) для всех \(i\), кроме начальной вершины. При добавлении вершины \(i\) в очередь \(visited[i]\) присваивается \(true\).

Теперь усложним задачу — нам нужно определить расстояние от первой вершины до всех остальных. Для этого создадим массив \(distance\). Данный массив нужен нам для хранения расстояния от первой вершины до всех остальных. Следует, что расстояние от вершины 1 до \(i\) хранится в \(distance[i]\). При посещении очередного соседа вершины \(current\) мы просто увеличим значение \(distance[current]\) на единицу.

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

Что такое bfs

BFS, или Breadth First Search — алгоритм обхода графа в ширину. Граф — это структура из «вершин» и «ребер», соединяющих между собой вершины. По ребрам можно передвигаться от одной вершине к другой, и BFS делает это поуровнево: сначала проходит по всем ближайшим от начальной точки вершинам, потом спускается глубже.

Освойте профессию «Data Scientist»

Выглядит это так: алгоритм начинает в заранее выбранной вершине и сначала «посещает» и отмечает всех соседей этой вершины. Потом он переходит к соседям посещенных вершин, затем — дальше по тому же принципу. Из-за характера распространения, похожего на волну, алгоритм еще называют волновым. BFS — один из двух популярных алгоритмов обхода. Второй называется DFS и подразумевает обход в глубину: сначала алгоритм проходит по ребрам «вглубь» графа.

Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.

Кто пользуется BFS

• Дата-сайентисты, которые работают с информацией и ее распространением, часто взаимодействуют с теорией графов.
• Разработчики, имеющие дело с определенными видами задач: поиск оптимального маршрута, программирование передвижения «умных» машин, разработка интеллектуальных систем и другие.
• Математики и другие ученые, которые работают с теорией графов как с фундаментальным научным знанием или в контексте решения практических задач.
• Инженеры-электроники: конкретно алгоритм BFS используется при трассировке печатных плат.
• Технические специалисты, работающие в телекоммуникационных системах. Там тоже активно применяется теория графов и в частности BFS.
• Сетевые инженеры, так как теория графов активно используется в сетевых технологиях. BFS, например, применяют при обходе P2P-сетей, или пиринговых сетей, а на них основаны многие сетевые протоколы. В частности, пиринговую сеть реализует BitTorrent.

Станьте дата-сайентистом и решайте амбициозные задачи с помощью нейросетей

Для чего нужен BFS

• Для решения задач поиска оптимального пути. Классической задачей считается автоматизированный поиск выхода из лабиринта.
• Для решения задач, связанных непосредственно с теорией графов, например для поиска компонент связности. Эти задачи в свою очередь решаются в Data Science, теории сетей и электронике.
• Для задач искусственного интеллекта, связанных с поиском решения с минимальным количеством ходов. В таком случае состояния «умной машины» представляются как вершины, а переходы между ними — как ребра.
• Для оптимизации памяти при обходе графа в некоторых ситуациях, например для некоторых специфических структур.
• Для работы с информацией в определенных структурах данных, таких как деревья. Их тоже можно обходить с помощью алгоритма BFS, потому что они — подвид графов.

Особенности BFS

• Константное количество действий для каждого ребра или вершины. Это важно при расчете сложности алгоритма — при выборе оптимального метода решения той или иной задачи.
• Отсутствие проблемы «бесконечного цикла»: алгоритм не попадет в него ни при каких условиях благодаря особенностям работы.
• Высокая точность и надежная архитектура, которая позволяет полагаться на этот алгоритм в решении различных задач.
• Возможность работать и с ориентированными, и с неориентированными графами. О том, чем они различаются, можно прочитать в статье про ориентированный граф.
• Полнота алгоритма — он найдет решение, то есть кратчайший путь, и завершится на любом конечном графе. Если граф бесконечный, решение найдется только в том случае, если конечен какой-либо из его путей.
• Возможность находить кратчайший путь в графе, если все ребра одинаковой длины. Если длины ребер разные, BFS найдет путь с минимальным количеством ребер, но он не обязательно будет самым коротким. Для поиска кратчайшего пути в таком случае будет лучше алгоритм Дейкстры.

Как работает алгоритм BFS

Алгоритм простой и интуитивно понятный. Он проходит по вершинам графа, пока в том не останется непосещенных вершин, и рассчитывает самый короткий путь до целевой вершины. Чтобы показать его работу нагляднее, представим алгоритм пошагово.

Начало работы. В качестве начальной можно выбрать любую вершину. На момент начала работы алгоритма все вершины помечены как непосещенные — их называют «белыми». Первое, что делает алгоритм, — помечает начальную вершину как посещенную (также используют термины «развернутая» или «серая»). Если она и есть целевая, на этом алгоритм завершается. Но чаще всего это не так.

Поиск соседей. Алгоритм проверяет, какие соседи есть у начальной вершины. Они добавляются в «очередь действий» в том порядке, в каком алгоритм их нашел, и тоже помечаются как «серые». Это продолжается, пока у начальной вершины не останется «белых» соседей.

Переход на следующую вершину. Когда алгоритм проходит по всем соседям начальной вершины, он помечает ее как полностью обойденную. Такие вершины еще называют «черными»: алгоритм к ним не возвращается. Затем он переходит к одной из «серых» вершин — соседей начальной. Алгоритм выбирает первую вершину в очереди. Далее действия повторяются: «соседи» вершины, кроме «черной», заносятся в очередь.

Когда и эта вершина будет пройдена, переход повторится по тому же принципу — первая вершина в очереди. В этом случае ею будет второй сосед начальной вершины — мы помним, что их добавляли в очередь первыми. И только когда соседи начальной вершины в очереди закончатся, алгоритм пойдет по следующему «уровню» вершин. Так и достигается обход в ширину.

Конец алгоритма. Если очередь оказалась пустой, это значит, что «белых» и «серых» вершин больше не осталось. Алгоритм завершится. Если при этом целевая вершина не будет достигнута, это значит, что доступа к ней из начальной точки нет.

Если целевая вершина достигается раньше, чем алгоритм пройдет по всему графу, это также может означать его завершение. Алгоритм остановится, потому что задача окажется выполнена: самый короткий путь к целевой вершине будет найден.

Как реализовать алгоритм BFS

Реализация алгоритма возможна на любом языке программирования, который вы знаете. Граф обычно представляется как массив, очередь или другая структура данных. Ее элементы — вершины, и в них хранятся сведения о других вершинах, с которыми они соединены. Иногда там напрямую есть ссылки на другие вершины — конкретная реализация зависит от языка программирования и выбранной архитектуры.

Алгоритм BFS, реализованный программно, начинает с заданного элемента этой структуры данных — это аналогично начальной вершине. Он отмечает ее посещенной, или «серой» — например, записывает в элемент какое-то значение-метку. Затем он смотрит, на какие элементы ссылается начальный, и отмечает посещенными уже их. Когда все ссылки на другие элементы в начальной вершине заканчиваются, граф помечает ее как полностью обойденную, «черную» — для этого используется другое значение-метка. Оно показывает алгоритму, что больше возвращаться в эту вершину нет смысла, — так он не «застрянет» в одних и тех же точках.

После этого алгоритм переходит по ссылке к первому найденному «соседу» этой вершины и повторяет те же действия. Это продолжается, пока все вершины не окажутся помеченными как полностью обойденные.

Вы можете подробнее познакомиться с теорией графов, ее задачами, методами их решения и программными реализациями этих методов на курсах SkillFactory.

Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.