BFS

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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