Deque

Дек — комбинация стека и очереди. В дек можно как добавлять, так и удалять элементы с обеих сторон. Поэтому дек так и называется — deque, от double-ended queue.

from collections import deque

empty_deque = deque() # Так можно создать пустой дек
my_deque = deque([1, 2, 3]) # А так — с несколькими элементами

Дек замечателен тем, что добавление или удаление элемента и в конец, и в начало занимает O(1) времени.

>>> from collections import deque
>>> my_deque = deque()
>>> my_deque.appendleft(1) # Добавим элементы слева
>>> my_deque.appendleft(2)
>>> my_deque
deque([2, 1])
>>> my_deque.append(-1) # Добавим элементы справа
>>> my_deque.append(-2)
>>> my_deque
deque([2, 1, -1, -2])
# Удалим пару элементов слева
>> my_deque.popleft()
2
>>> my_deque.popleft()
1
# Удалим пару элементов справа
>>> my_deque.pop()
-2
>>> my_deque.pop()
-1
>>> my_deque
deque([])

Элементы можно добавлять не только по одному, для этого существуют методы extend и extendleft, которые принимают последовательности и по очереди добавляют их элементы в очередь:

from collections import deque
>>> my_deque = deque()
>>> my_deque.extend([1, 2, 3])
>>> my_deque
deque([1, 2, 3])
>>> my_deque.extendleft([4, 5, 6])
>>> my_deque
deque([6, 5, 4, 1, 2, 3])

На этом интересующие нас методы заканчиваются, все остальные см. в документации.

BFS

BFS расшифровывается как breadth-first search — поиск в ширину.
Идея поиска в ширину в том, чтобы обходить сначала вершины наиболее близкие к текущей вершине. Именно для этого используется очередь.

Алгоритм:
1. Поместить вершину, из которой начинается поиск в изначально пустую очередь
2. Извлечь из начала очереди вершину и покрасить её в черный цвет.
- Если вершина является искомой, то завершить поиск.
- Если нет, то добавить в конец очереди все вершины смежные данной и покрасить их в серый цвет.
3. Если очередь оказывается пустой, то все вершины были просмотрены, следовательно искомая вершина недостижима из начальной.
4. Если очередь не пуста, то вернуться в п. 2.

DFS vs BFS

Обходить граф просто так довольно бесполезно. Обычно нас интересует либо длина минимального пути от одной вершины до другой, либо сам минимальный путь.
Давайте заведем отдельный список, в котором будем хранить длину пути от начальной вершины до i-той. Тогда при рассмотрении смежных (v) с u вершин нам будет достаточно написать distance[v] = distance[u] + 1.

Но что делать, когда нам нужна не только длина кратчайшего пути, но и он сам?
В этом случае мы заводим еще один список (previous), в котором по i-тому индексу хранится вершина, из которой BFS пришел в i-тую вершину.
Имея список previous несложно восстановить путь.

Поиск в ширину в лабиринте

Лабиринт не похож на граф, но на самом деле с ним можно работать как с графом. Для каждой клетки мы знаем соседей: это клетки с координатами (x±1, y±1). Удобно пройтись по соседям можно так:

NEIGHBOURS = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for dx, dy in NEIGHBOURS:
    if ... # проверяем, можно ли пройти 
           # в эту соседнюю клетку