Алгоритм поиска в ширину (BFS) в Python

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

К концу этого урока вы научитесь следующему:

• Что такое алгоритм поиска в ширину и как его реализовать с помощью псевдокода

• Как реализовать поиск в ширину в Python с нуля

• Как реализовать алгоритм поиска в ширину на Python с использованием библиотеки NetworkX

Оглавление

• Понимание алгоритма поиска в ширину

• Псевдокод для поиска в ширину

• Реализация поиска в ширину в Python с нуля

• Реализация поиска в ширину в Python с использованием NetworkX

• Заключение

Понимание алгоритма поиска в ширину

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

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

Давайте рассмотрим пример. Представим, что у нас есть следующий граф, и мы хотим пройти по всем узлам, начиная с узла 'A'

Для этого создадим два объекта:

1. Очередь используется для отслеживания добавляемых элементов по методу первым пришел — первым ушел.

2. Множество, для отслеживания узлов, которые мы уже посетили

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

На изображении выше мы переместили наш посещенный узел в наш набор посещенных узлов. Это позволяет нам гарантировать, что мы случайно не посетим его снова. Мы также добавили единственного соседа 'B' в нашу очередь. На изображении это выделено темным кругом, что указывает на то, что мы собираемся посетить его в ближайшее время.

На следующем шаге мы переходим к B. При этом мы удаляем его из нашей очереди и добавляем в наш набор посещенных. Затем мы проверяем всех его соседей, которыми в данном случае являются 'C' и 'D', и добавляем их в нашу очередь.

После этого мы затем берем самый левый элемент в нашей очереди и посещаем его. Мы добавляем его в наш набор посещенных и обнаруживаем всех его соседей. Поскольку 'B' уже был посещен, мы не добавляем его в нашу очередь. Вместо этого мы добавляем только 'E'.

Затем мы снова берем самый левый элемент из нашей очереди и посещаем его. Мы ищем всех его соседей и добавляем их в нашу очередь.

Затем мы посещаем 'E', наш самый левый элемент в очереди. Поскольку у 'E' нет соседей, которых мы еще не посетили, мы ничего не добавляем в очередь.

На последнем этапе мы посещаем 'F'. Поскольку у 'F' нет соседей, которых мы еще не видели, наш поиск в ширину здесь заканчивается.

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

Псевдокод для поиска в ширину

Написание некоторого псевдокода для алгоритма поиска в ширину даст нам крепкую основу для его реализации на Python. Давайте посмотрим, как выглядит этот псевдокод:

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

Давайте разберем, что делает наш псевдокод:

1. Мы создаем очередь для хранения узлов, которые предстоит посетить

2. Мы отмечаем нашу начальную вершину как посещенную и помещаем ее в очередь

3. Мы затем используем цикл while для продолжения, пока в очереди есть элементы

4. В нашем цикле мы сначала удаляем первый элемент и помечаем его как посещённый. Затем мы добавляем всех непосещённых соседей в очередь.

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

Реализация поиска в ширину в Python с нуля

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

Мы начнем с реализации нашего графа как списка смежности. Это создает словарь, который содержит все узлы нашего графа в виде ключей. Значения каждого ключа - это список (или множество), содержащий все соседние узлы.

# Представление нашего графа в виде списка смежности
graph = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['B', 'E'],
    'D': ['B', 'E', 'F'],
    'E': ['C', 'D'],
    'F': ['D'],
}

Теперь, когда у нас есть разработанный граф, давайте создадим функцию для реализации алгоритма поиска в ширину (BFS) на Python. Наша функция будет принимать два параметра:

1. Наш граф представлен в виде списка смежности,

2. Наш стартовый узел

Давайте посмотрим, как выглядит эта функция:

from collections import deque

def bfs(graph, start_node): 
  # Инициализация пустого множества для посещенных узлов
  visited = set()

  # Инициализация пустой очереди для обхода
  queue = deque()

  # Добавление начального узла
  visited.add(start_node)
  queue.append(start_node)

  # Пока в очереди есть элементы
  while queue:
    # Удаление элемента из очереди
    m = queue.popleft()

    # Проверка всех соседних узлов
    for neighbour in graph[m]:

      # Если сосед еще не посещен
      if neighbour not in visited:
        visited.add(neighbour)
        queue.append(neighbour)
        
  return visited

Хотя это выглядит как большой объем кода, большая его часть — это просто комментарии, которые помогут вам разобраться в том, что происходит. Давайте разберем это шаг за шагом:

1. Инициализация:

   • Инициализируется пустое множество visited для отслеживания посещенных узлов.

   • Инициализируется deque (двусторонняя очередь) под названием queue для обхода.

2. Начальный узел:

   • Начальный узел добавляется как в visited, так и в queue для начала обхода.

3. Обход в ширину (BFS):

   • Цикл while продолжается до тех пор, пока queue не станет пустым.

   • Внутри цикла он извлекает самый левый узел (m) из очереди.

   • Затем он итерирует по соседям m, используя for neighbour in graph[m].

4. Посещение Соседей:

   • Для каждого соседа:

     • Если сосед не был посещён (проверяется с помощью if neighbour not in visited):

       • Добавляет соседа в множество visited.

       • Помещает соседа в очередь queue для дальнейшего исследования.

5. Возврат Посещенных Узлов:

   • После завершения обхода функция возвращает набор visited, содержащий все посещенные узлы, доступные из start_node.

Давайте теперь реализуем эту функцию и посмотрим, что у нас получится!

# Использование нашей функции обхода в ширину
print(bfs(graph, 'A'))

# Возвращает:
# {'A', 'B', 'C', 'D', 'E', 'F'}

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

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

Реализация поиска в ширину в Python с использованием NetworkX

Мы можем использовать библиотеку Python NetworkX для реализации поиска в ширину. Поскольку эта библиотека не встроена в Python, нам сначала необходимо установить ее. Мы можем сделать это, используя менеджер пакетов pip и введя показанную ниже команду в ваш терминал:

pip install networkx

NetworkX позволяет легко реализовать графы на Python. Например, вы можете передать список смежности, который мы использовали, чтобы создать объект графа. Давайте посмотрим, как это выглядит:

# Создание объекта графа NetworkX
import networkx as nx
graph = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['B', 'E'],
    'D': ['B', 'E', 'F'],
    'E': ['C', 'D'],
    'F': ['D'],
}

G = nx.Graph(graph)
print(G)

# Возвращает: Граф с 6 узлами и 6 рёбрами

В приведенном выше блоке кода мы сначала импортировали NetworkX с использованием псевдонима nx. Затем мы использовали тот же список смежности для представления нашего графа. Мы передали это в конструктор класса Graph(). Наконец, мы распечатали наш граф, возвращая некоторую общую информацию о графе.

Мы можем использовать ряд различных функций поиска в ширину, которые доступны в библиотеке NetworkX. Чтобы увидеть, как библиотека будет осуществлять обход нашего графа, мы можем использовать функцию bfs_tree(). Функция осуществляет обход данного графа, используя предоставленный начальный узел:

# Реализация BFS в NetworkX
bfs = list(nx.bfs_tree(G=G, source='A'))
print(bfs)

# Возвращает: 
['A', 'B', 'C', 'D', 'E', 'F']

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

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

Заключение

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

Мы изучили алгоритм поиска в ширину (BFS) шаг за шагом, поняв его механику на примере и разработав четкое представление в виде псевдокода. Затем мы реализовали BFS как с нуля, так и с использованием библиотеки NetworkX. Код на Python продемонстрировал элегантную простоту реализации BFS, предложив мощный инструмент для эффективного обхода графов. Кроме того, NetworkX продемонстрировала свою полезность в упрощении обработки графов и выполнения BFS, обеспечивая беспроблемную альтернативу для операций трассировки. Независимо от того, предпочитаете ли вы практический подход или использование библиотек, таких как NetworkX, освоение BFS наделяет разработчиков Python фундаментальным алгоритмическим инструментом для исследования графов и решения задач.