Дек — комбинация стека и очереди. В дек можно как добавлять, так и удалять элементы с обеих сторон. Поэтому дек так и называется — 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 расшифровывается как breadth-first search — поиск в ширину.
Идея поиска в ширину в том, чтобы обходить сначала вершины наиболее близкие к текущей вершине. Именно для этого используется очередь.
Алгоритм:
1. Поместить вершину, из которой начинается поиск в изначально пустую очередь
2. Извлечь из начала очереди вершину и покрасить её в черный цвет.
- Если вершина является искомой, то завершить поиск.
- Если нет, то добавить в конец очереди все вершины смежные данной и покрасить их в серый цвет.
3. Если очередь оказывается пустой, то все вершины были просмотрены, следовательно искомая вершина недостижима из начальной.
4. Если очередь не пуста, то вернуться в п. 2.
Обходить граф просто так довольно бесполезно. Обычно нас интересует либо длина минимального пути от одной вершины до другой, либо сам минимальный путь.
Давайте заведем отдельный список, в котором будем хранить длину пути от начальной вершины до 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 ... # проверяем, можно ли пройти
# в эту соседнюю клетку