«Обход в ширину» или «Поиск в ширину» (Breadth first traversal or Breadth first Search) - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных.
Для простоты предполагается, что все вершины достижимы из начальной вершины. BFS использует для обхода структуру данных: очередь (queue)
Стандартная реализация ВFS помещает каждую вершину графа в одну из двух категорий:
- Посещенные.
- Не посещенные.
Цель алгоритма - пометить каждую вершину, как посещенную, избегая циклов.
Алгоритм работает следующим образом:
- Начните с размещения любой вершины графа в конце очереди.
- Возьмите передний элемент очереди и добавьте его в список посещенных.
- Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в конец очереди.
- Продолжайте повторять шаги 2 и 3, пока очередь не опустеет.
Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере. Мы используем неориентированный граф с 5 вершинами.
Мы начнем с вершины 0, алгоритм BFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.
Затем мы посещаем элемент в начале очереди, то есть 1, и переходим к соседним узлам. Так как 0 уже был посещен, мы посещаем 2.
У вершины 2 есть соседняя не посещенная вершина 4, поэтому мы добавляем ее в конец очереди и посещаем 3, которая находится в начале очереди.
В очереди остается только 4, поскольку единственный соседний узел с 3, то есть 0, уже посещен. Мы посещаем вершину 4.
Поскольку очередь пуста, мы завершили обход в ширину графика.
import collections
def bfs(graph, root):
visited, queue = set(), collections.deque([root])
visited.add(root)
while queue:
vertex = queue.popleft()
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return visited
if __name__ == '__main__':
graph = {0: [1, 2], 1: [2], 2: [3], 3: [1,2]}
print(bfs(graph, 0))
Создаём 2 структуры: множество и двустороннюю очередь в которую помещаем нашу вершину.
Добавляем во множество значение нашего корня (начальной вершины).
Начинаем цикл до тех пор пока все дети не закончатся:
удаляем текущую вершину из очереди, и проходим циклом по её детям, добавляем в наше множество этих детей, добавляем их в очередь, чтобы в дальнейшем найти и их детей и так далее.
Для деревьев этот алгоритм также называется Level Order Traversal - Техника обхода порядка уровней или BFS - Breadth first Search (обход в ширину) определяется как метод обхода дерева, при котором все узлы, присутствующие на одном уровне, проходятся полностью перед переходом на следующий уровень.
Большая часть материала украдена с сайта https://evileg.com/ru/post/512/