pattern heroPT–23LeetCode Extension

Поиск в ширину (BFS)

Обходим волнами: сначала всё рядом со стартом, потом всё на шаг дальше. Поэтому до каждого места доходим впервые по самому короткому пути, и перебирать пути не нужно.

Вариант
P15 Поиск в ширину (BFS)Узлы дерева · 1×

Пример задачи: выписать значения двоичного дерева по уровням. Каждый узел — объект с полями val, left и right; отсутствующий потомок — none.

nonenonenonenonenonenone3920157очередьначало слева—
не достигнутждёт в очередитекущийготовnone: пустой потомок

Уровней пока нет: result = []

result = []queue = –level = –size = –node = –
01/45
сначала · назад · пуск · шаг
Скорость
1function levelOrder(root):
2 result = []
3 queue = [root]
4 while queue is not empty:
5 level = []
6 size = queue.size
7 repeat size times:
8 node = queue.popFront()
9 level.add(node.val)
10 if node.left is not none:
11 queue.pushBack(node.left)
12 if node.right is not none:
13 queue.pushBack(node.right)
14 result.add(level)
15 return result

← → шаг · пробел — пауза

Как узнать

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

Как решать такие задачи

  1. Если корень может быть none, сразу верни пустой ответ.
  2. Положи корень в очередь.
  3. В начале каждого круга запомни size = queue.size и возьми ровно столько узлов: это один уровень.
  4. Клади левого и правого потомка каждого узла в конец, пропуская none. Для самого правого значения, среднего или зигзага меняется только то, что ты делаешь с уровнем.

Вариант: Граф

То же, но в графе к одной вершине ведут разные пути, поэтому посещённые вершины отмечаем. Первый раз, когда волна дошла до вершины, — это самый короткий путь до неё.

  1. Определи, что здесь вершина (клетка, слово, состояние) и кто её соседи.
  2. Положи старт в очередь и сразу отметь посещённым.
  3. Бери из начала. Каждого непосещённого соседа клади в конец и сразу отмечай.
  4. Для расстояний иди по уровням или храни расстояние вместе с вершиной. Остановись, когда дошёл до цели.

Вариант: Сетка

То же, но на сетке: клетки — это вершины, а соседние клетки связаны. Волна расходится от старта, и шаг, на котором она дошла до клетки, — это кратчайшее расстояние до неё.

  1. Считай каждую открытую клетку вершиной: её соседи — клетки сверху, снизу, слева и справа, которые внутри сетки и не стены.
  2. Заведи таблицу dist, заполненную none. Поставь старту 0 и положи его в очередь.
  3. Бери клетку из начала. Каждому соседу без расстояния ставь на 1 больше, чем у неё, и клади его в конец.
  4. Останавливайся, когда цель выходит из очереди: её расстояние уже окончательное. Клетка, до которой не дошли, остаётся none.
  5. Если источников несколько, например все гнилые апельсины сразу, положи их все в очередь с расстоянием 0 до начала цикла.

Вариант: Состояния

То же, но вершины — не места, а состояния, например слова, которые отличаются одной буквой. Граф заранее не строим: соседей состояния придумываем, когда до него дошли.

  1. Реши, что такое одно состояние: слово, положение колёсиков замка, клетка на доске. Один ход — одно ребро.
  2. Напиши функцию, которая строит соседей состояния; весь граф заранее строить не нужно.
  3. Запусти BFS от старта и храни число ходов в dist. Состояние, которое уже есть в dist, пропускают, поэтому в очередь ничего не попадает дважды.
  4. Настольная игра устроена так же: в «Змеях и лестницах» каждая клетка — вершина, бросок кубика даёт до шести соседей, а змея или лестница переносит дальше, прежде чем клетку кладут в очередь.

Где встречается

  • Скачивание сайта. wget --recursive скачивает сайт волнами: сначала стартовую страницу, потом страницы по ссылкам с неё, потом следующий слой. Ключ -l ограничивает, сколько волн пройти.
  • Сборка мусора. Копирующий сборщик мусора по алгоритму Чейни переносит живые объекты в новую область волнами: сначала те, на которые ссылается программа, потом те, на которые ссылаются они. Очередью служит сама новая область памяти.