На этом шаге мы рассмотрим ее реализацию.

    Для реализации алгоритма BFS нужна структура данных, известная как очередь. Если стек - это структура LIFO, то очередь - структура FIFO (first-in-first-out, "первым вошел - первым вышел"). Очередь встречается нам и в обычной жизни - например, цепочка людей, ожидающих у входа в магазин. Кто раньше занял очередь, тот первым туда идет. Очередь как минимум имеет те же методы push() и рор(), что и стек. В сущности, реализация Queue на основе имеющегося в Python типа deque практически идентична реализации Stack, единственными изменениями являются удаление элементов с левого, а не с правого конца _container и замена list на deque (мы используюем здесь слово "левый" для обозначения начала резервного хранилища). Элементы, расположенные с левого края, - это самые старые элементы, все еще находящиеся в deque (с точки зрения времени попадания в хранилище), поэтому они являются первыми извлекаемыми элементами (файл generic_search.py).

class Queue(Generic[T]):
    def __init__(self) -> None:
        self._container: Deque[T] = Deque()

    @property
    def empty(self) -> bool:
        return not self._container  # не равно True для пустого контейнера

    def push(self, item: T) -> None:
        self._container.append(item)

    def pop(self) -> T:
        return self._container.popleft()  # FIFO

    def __repr__(self) -> str:
        return repr(self._container)

Почему в реализации Queue в качестве резервного хранилища применяется deque, тогда как в реализации Stack использован list? Это связано с тем, откуда извлекаются данные в процессе операции pop. В стеке мы помещаем элементы с правого конца и извлекаем их тоже справа. В очереди мы помещаем элементы справа, а извлекаем слева. Структура данных list в Python имеет эффективный метод pop для извлечения справа, но не слева. Структура данных deque позволяет эффективно извлекать данные с любой стороны. Так что в deque есть встроенный метод popleft(), у которого нет эквивалента в list. Конечно, можно было бы найти другие способы применения list в качестве резервного хранилища для очереди, но они были бы менее эффективными. Извлечение данных слева в deque - это операция сложности O(1), тогда как для list это операция сложности O(n). В случае применения list после извлечения данных слева каждый последующий элемент должен быть сдвинут на одну позицию влево, что делает этот тип данных неэффективным.

    На следующем шаге мы рассмотрим алгоритм BFS.

Предыдущий шаг Содержание Следующий шаг