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

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

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

После того как вы знаете что такое графы и разобрались с базовым синтаксисом по программированию на Python – можно приступать к изучению алгоритма поиска в ширину! Алгоритм поиска в ширину или алгоритм BFS(Breadth-First Search) позволяет найти кратчайшее расстояние между двумя объектами. Однако термин "кратчайшее расстояние" может иметь много трактовок и значений в разных задачах! Например, с помощью алгоритма поиска в ширину можно:

• реализовать проверку правописания через минимальное количество изменений, преобразующих ошибочно написанное слово в правильное.
• Например: АЛГОРИФМ → АЛГОРИТМ – одно изменение;
• найти ближайшего к вам врача с помощью анализа карты в виде графа;
• создать поиск или поискового робота.

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

• тип 1: существует ли путь от узла А к узлу В?
• тип 2: как выглядит кратчайший путь от узла А к узлу В?

Начнём с типа 1. Представьте что вы выращиваете яблоки. Вы ищите продавца, который будет продавать их. А может продавец найдётся среди ваших друзей во вконтакте? Для начала стоит поискать среди друзей. Поиск происходит вполне тривиально. Сначала нужно построить список ближайших друзей для поиска. Затем обратиться к каждому другу в списке и проверить, продает ли этот друг яблоки. Допустим, что ни один из ваших друзей не продаёт яблоки. Теперь поиск продолжается среди друзей ваших друзей. Каждый раз, когда вы проверяете кого-то из списка, вы добавляете в список всех его друзей. В таком случае поиск ведётся не только среди друзей, но и среди друзей ваших друзей тоже. Напомню: нужно найти в сети хотя бы одного продавца яблок. Если например, друг Иван, не продаёт яблоки, то в список добавляются его друзья. Это означает, что со временем вы проверите всех его друзей, а потом их друзей и т.д. С этим алгоритмом поиск рано или поздно пройдёт по всей сети, пока вы все-таки не наткнетесь на продавца яблок. Такой алгоритм и называется поиском в ширину.

Поиск кратчайшего пути

Удастся ли вам найти ближайшего продавца яблок? Будем считать, что ваши друзья — это связи первого уровня, а друзья ваших друзей — связи второго уровня и т.д. Связи первого уровня предпочтительнее связей второго уровня, а связи второго уровня предпочтительнее третьего и т.д. Отсюда следует, что поиск по контактам второго уровня не должен производиться, пока вы не будите полностью уверены в том, что среди связей первого уровня нет ни одного продавца яблок. Поиск в ширину именно означает, что связи первого уровня будут проверены до связей второго уровня. Также можно объяснить это иначе: связи первого уровня будут добавлены в очередь или список поиска раньше связей второго уровня. Вы двигаетесь при поиске по списку и по очереди проверяете каждого человека, является ли он продавцом яблок. Связи первого уровня будут проверены до связей второго уровня, так что вы найдёте продавца яблок, ближайшего к вам. Поиск в ширину находит не только существует ли путь из точки А в точку В, но и кратчайший путь. Обратите внимание: это условие выполняется только в том случае, если поиск осуществляется в порядке добавления людей. Следовательно, проверять связи необходимо в порядке их добавления. Для операций такого рода существует специальная структура данных, которая называется очередью.

Очереди

Очередь в программировании работает точно также, как и в реальной жизни. Предположим, вы с другом стоите в очереди метро. Если вы стоите ближе к началу очереди, то первыми сядете в метро. Структура данных очереди работает аналогично. Очереди похожи на стеки: вы не можете выполнить действия над произвольным элементом. Вместо этого поддерживаются только две операции: постановка в очередь и извлечение из очереди. Очередь относится к категории структур данных FIFO(First In, First Out) "первым вошёл, первым вышел". А стек принадлежит к числу структур данных LIFO(Last In, First Out) "последним вошёл, первым вышел". Если вы поставите в очередь два элемента, то элемент, добавленный первым, будет извлечён из очереди раньше второго. Это можно использовать для реализации списка поиска людей. Люди, добавленные в список первыми, будут извлечены из очереди и проверены первыми. Теперь когда вы понимаете, как работает очередь, можно приступать к реализации алгоритма поиска в ширину!

Реализация графа

Для начала необходимо реализовать граф на программном уровне. Граф состоит из нескольких узлов. И каждый узел соединяется с соседними узлами. Как выразить отношения вы и ваши друзья? Вам уже должна быть знакома такая структура данных как: хеш-таблица. Вспомните: хеш-таблица связывает ключ со значением. В данном случае узел должен быть связан со всеми его внешними соседями. Вот как это на Python:

graph = {}
graph["вы"] = ["Иван", "Пётр", "Нина"]

Обратите внимание: элемент "вы" отображается на массив. Следовательно, результатом выражения graph["вы"] является массив всех ваших внешних соседей. Помните, что внешние соседи — это узлы, к которым обращается узел "вы". Граф — всего лишь набор узлов и рёбер, поэтому для представления графа на Python ничего больше не потребуется. А как насчёт большего графа? Например такого:

graph = {}
graph["вы"] = ["Иван", "Пётр", "Нина"]
graph["Иван"] = ["Владимир", "Степан"]
graph["Пётр"] = ["Семён", "Светлана"]
graph["Нина"] = ["Светлана"]
graph["Владимир"] = []
graph["Светлана"] = []
graph["Семён"] = []
graph["Степан"] = []

Важен ли порядок добавления пар "ключ" — "значение"? Нет, не важен. В хеш-таблице(или словарь Python) элементы не упорядочены, поэтому добавлять пары "ключ — значение" можно в любом порядке. У Владимира, Светланы, Семёна и Степана внешних соседей нет. У них есть внутренние соседи, поскольку линии со стрелками указывают на них, но не существует стрелок от них к другим узлам. Такой граф называется направленным — отношения действуют только в одну сторону. В ненаправленном графе стрелок нет. Например, оба следующих графа эквиваленты. В ненаправленных графах не существует деления соседей на "внутренних" и "внешних" — это просто "соседи".

Реализация алгоритма

Всё начинается с создания очереди. В Python создания двусторонней очереди("дека") используется функция deque:

from collections import deque
search_queue = deque() # Создание очереди
search_queue += graph["вы"] # Все соседи добавляются в очередь поиска

Выражение graph["вы"] вернёт список всех ваших соседей, например ["Иван", "Пётр", "Нина"]. Все они добавляются в очередь поиска. Далее рассмотрим остальное:

while search_queue: # пока очередь не опустеет
    person = search_queue.popleft() # из очереди извлекается первый стоящий в ней элемент
    # Проверка, не проверяли ли мы уже этого человека(элемент из очереди)
    if person in searched:  # Отдельное множество элементов searched, в котором храним уже проверенные элементы
        continue
    if is_seller(person): # Проверяем является ли этот человек продавцом(является ли элемент тем, который мы ищем)
        print(person + " это продавец яблок!")
    search_queue += graph[person] # Нет, не является. Все соседи этого элемента добавляются в очередь.
    # Отмечаем что мы проверяли текущий элемент
    searched.add(person)

Затем нужно определить функцию проверки, в нашем примере пусть она называется: is_seller. Пусть она определит просто является ли человек продавцом яблок или нет. Например, пусть функция будет выглядеть так:

def is_seller(name):
      return name[-1] == 'а'

Проверка довольно-таки глупая, но она здесь просто для примера. Эта функция проверяет, заканчивается ли имя человека на букву 'а', и если заканчивается, будем считать его продавцом яблок. Алгоритм будет работать до тех пор, пока:

• не будет найден продавец яблок;
• очередь не опустеет(в этом случае продавца не нашли).

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

Ну и наконец посмотрим на окончательную версию кода поиска в ширину, в которой учтены все обстоятельства:

from collections import deque

def is_seller(name):
      return name[-1] == 'а'

graph = {}
graph["вы"] = ["Иван", "Пётр", "Нина"]
graph["Иван"] = ["Владимир", "Степан"]
graph["Пётр"] = ["Семён", "Светлана"]
graph["Нина"] = ["Светлана"]
graph["Владимир"] = []
graph["Светлана"] = []
graph["Семён"] = []
graph["Степан"] = []

def search(name):
    search_queue = deque() # Создание очереди
    search_queue += [name] # Все соседи добавляются в очередь поиска
    
    # Через множество, вы можете отслеживать, кого из людей вы уже проверяли ранее
    searched = set()
    
    while search_queue: # пока очередь не опустеет
        person = search_queue.popleft() # из очереди извлекается первый стоящий в ней элемент
        # Проверка, не проверяли ли мы уже этого человека(элемент из очереди)
        if person in searched:
            continue # начинаем новую итерацию цикла
        if is_seller(person): # Проверяем является ли этот человек продавцом(является ли элемент тем, который мы ищем)
            print(person + " это продавец яблок!")
            return True # выходим из функции так как нашли то что искали
        search_queue += graph[person] # Нет, не является. Все соседи этого элемента добавляются в очередь.
        # Отмечаем что мы проверяли текущий элемент
        searched.add(person)
    return False  # Возвращаем по окончанию цикла False, т.к. не нашли то что искали

search("вы")  # Пример запуска функции поиска в ширину

Выполните этот код самостоятельно. Замените функцию is_seller чем-то более содержательным и посмотрите, определит ли она то что вы ожидали.

Попробуйте сами скопировать и запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.

Топологическая сортировка

Итак, подведём некоторый итог по данному алгоритму. Рассмотрим такое понятие как топологическая сортировка. Алгоритм поиска в ширину (BFS, Breadth-First Search) может использоваться для топологической сортировки — упорядочивания вершин ориентированного графа так, чтобы каждое ребро u → v шло от более ранней вершины к более поздней. Иначе говоря, если вершина v зависит от u, то в порядке прохождения u всегда стоит перед v.

Топологическая сортировка — термин из теории графов, который означает линейное упорядочивание вершин ориентированного ациклического графа (DAG — Directed Acyclic Graph). Топологическая сортировка возможна только для направленных ациклических графов (DAG). Если в графе есть цикл, корректного топологического порядка не существует.

Существует два основных алгоритма построения топологической сортировки:

• Алгоритм Кана. Находит все вершины с нулевой входящей степенью (то есть те, от которых ничего не зависит), добавляет их в очередь. Удаляет вершину из графа, уменьшая входящие степени её соседей. Повторяет процесс, пока не обработаны все вершины. Если в процессе остаются вершины с ненулевой входящей степенью, значит, в графе есть цикл — топологическая сортировка невозможна.
• Алгоритм на основе поиска в глубину (DFS). Обходит граф в глубину, после обработки всех соседей вершины добавляет её в стек. Финальный порядок — это обратный порядок извлечения из стека.

В следующей статье рассмотрен Алгоритм DFS. Поиск в глубину

Для топологической сортировки с помощью BFS используется алгоритм Кана. Этот алгоритм мы и реализовали в примере выше. Ещё раз пропишем его шаги:

1. Вычислить степень каждой вершины — количество входящих рёбер.
2. Добавить в очередь все вершины со степенью 0, так как они могут появиться первыми в порядке.
3. Повторяемо удалять вершину из очереди, добавлять её в список результата и уменьшать степень всех её смежных вершин. Если у какой-то из этих вершин теперь степень 0, её добавляют в очередь.
4. Этот процесс продолжается, пока очередь не станет пустой, и полученный порядок представляет один допустимый топологический порядок графа.

Время выполнения алгоритма

Если поиск продавца яблок был выполнен по всей сети, значит, вы прошли по каждому ребру графа из очереди. Таким образом, время выполнения составляет как минимум O(количество рёбер). Также в программе должна храниться очередь поиска. Добавление одного элемента в очередь выполняется за постоянное время: O(1). Выполнение операции для каждого элемента потребует суммарного времени O(количество элементов). Поиск в ширину выполняется за время O(количество элементов + количество рёбер), что обычно записывается в форме O(V + E). V — количество элементов или вершин; E — количество рёбер или связей между вершинами.