BFS: встречается на 60% алгоритмических собеседованиях, но как научиться видеть этот алгоритм в задачах
BFS — один из тех алгоритмов, который легко понять, но сложно научиться узнавать в новых задачах.
Поэтому не будем начинать с определения, начнем с простой задачи.
Есть дерево:
1
/ \
2 3
/ \ \
4 5 6
Нужно получить значения по уровням:
1
2 3
4 5 6
Как это сделать?
Нам нужно сначала обработать 1.
Только после этого перейти к 2 и 3.
И только потом к 4, 5, 6.
То есть мы двигаемся слой за слоем - это и есть основная идея BFS.
Как это реализовать? Лучшая структура данных - очередь.
Сначала кладем туда корень:
Queue:
[1]
Достаем 1.
Добавляем его детей:
[2, 3]
Достаем 2.
Добавляем его детей:
[3, 4, 5]
Достаем 3.
Получаем:
[4, 5, 6]
И так продолжаем, пока очередь не станет пустой. Реализация на Java имеет вид:
Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node current = queue.poll();
for (Node child : current.children) {
queue.offer(child);
}
}
Что выполняет этот код:
- Создаётся очередь (интерфейс Queue) с конкретной реализацией ArrayDeque
- Очередь будет хранить узлы типа Node
- В очередь помещается корневой узел дерева (если он не null, иначе позже будет NullPointerException).
- while (!queue.isEmpty()) { Пока очередь не пуста, выполняется цикл. Это означает, что есть узлы, которые нужно посетить (offer добавляет элемент в конец очереди и возвращает true)
- Node current = queue.poll(); -Извлекается и удаляется первый элемент из очереди (голова).
- Для каждого дочернего узла текущего узла (предполагается, что у Node есть поле children — коллекция или массив) выполняется offer, т.е. все дети добавляются в конец очереди
Вот и весь базовый BFS, но как понять, что в задаче нужен BFS? Вот это гораздо важнее самого кода.
Можно выделить несколько сигналов:
1. Нужно пройти по уровням
Например, вывести дерево по уровням.→ BFS
2. Нужно найти ближайший объект
Например, найти ближайшую клетку с выходом.→ скорее всего BFS
3. Нужно найти минимальное количество шагов
Например, за сколько ходов можно попасть из точки A в точку B? Если каждый переход имеет одинаковую стоимость:
→ BFS
Почему? Потому что BFS сначала проверяет расстояние 1, потом 2, потом 3 и так далее.
Первый найденный путь будет кратчайшим.
А теперь интереснее
Допустим, у нас есть лабиринт:
S . . #
# . . #
# . . E
Нужно найти кратчайший путь от S до E.
Мы можем идти:
S
↓
1 шаг
↓
2 шага
↓
3 шага
...
BFS будет распространяться от S одновременно во все доступные стороны.
Как только дойдет до E — мы нашли минимальное количество шагов.
А что делать, если стартовых точек несколько?
Например, есть несколько зараженных клеток, и заражение распространяется каждую минуту, тогда мы можем положить все стартовые клетки в очередь сразу.
Это называется: Multi-Source BFS.
Именно так решается, например, задача Rotting Oranges.
Как учить BFS на практике?
Не нужно решать 30 одинаковых задач.
Лучше идти по нарастающей:
1. Binary Tree Level Order Traversal
Учимся самому BFS.
2. Shortest Path
BFS + расстояние.
3. Rotting Oranges
Multi-Source BFS.
4. Word Ladder
BFS по графу, которого напрямую вообще нет.
И вот здесь начинается самое интересное:
- в задаче с деревом граф очевиден
- в лабиринте граф — это клетки
- в Word Ladder граф — это возможные слова и переходы между ними.
То есть на более сложных задачах сначала нужно увидеть граф.
В следующих постах я детально разберу решение данных задач.
BFS — один из тех алгоритмов, который легко понять, но сложно научиться узнавать в новых задачах.
Поэтому не будем начинать с определения, начнем с простой задачи.
Есть дерево:
1
/ \
2 3
/ \ \
4 5 6
Нужно получить значения по уровням:
1
2 3
4 5 6
Как это сделать?
Нам нужно сначала обработать 1.
Только после этого перейти к 2 и 3.
И только потом к 4, 5, 6.
То есть мы двигаемся слой за слоем - это и есть основная идея BFS.
Как это реализовать? Лучшая структура данных - очередь.
Сначала кладем туда корень:
Queue:
[1]
Достаем 1.
Добавляем его детей:
[2, 3]
Достаем 2.
Добавляем его детей:
[3, 4, 5]
Достаем 3.
Получаем:
[4, 5, 6]
И так продолжаем, пока очередь не станет пустой. Реализация на Java имеет вид:
Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node current = queue.poll();
for (Node child : current.children) {
queue.offer(child);
}
}
Что выполняет этот код:
- Создаётся очередь (интерфейс Queue) с конкретной реализацией ArrayDeque
- Очередь будет хранить узлы типа Node
- В очередь помещается корневой узел дерева (если он не null, иначе позже будет NullPointerException).
- while (!queue.isEmpty()) { Пока очередь не пуста, выполняется цикл. Это означает, что есть узлы, которые нужно посетить (offer добавляет элемент в конец очереди и возвращает true)
- Node current = queue.poll(); -Извлекается и удаляется первый элемент из очереди (голова).
- Для каждого дочернего узла текущего узла (предполагается, что у Node есть поле children — коллекция или массив) выполняется offer, т.е. все дети добавляются в конец очереди
Вот и весь базовый BFS, но как понять, что в задаче нужен BFS? Вот это гораздо важнее самого кода.
Можно выделить несколько сигналов:
1. Нужно пройти по уровням
Например, вывести дерево по уровням.→ BFS
2. Нужно найти ближайший объект
Например, найти ближайшую клетку с выходом.→ скорее всего BFS
3. Нужно найти минимальное количество шагов
Например, за сколько ходов можно попасть из точки A в точку B? Если каждый переход имеет одинаковую стоимость:
→ BFS
Почему? Потому что BFS сначала проверяет расстояние 1, потом 2, потом 3 и так далее.
Первый найденный путь будет кратчайшим.
А теперь интереснее
Допустим, у нас есть лабиринт:
S . . #
# . . #
# . . E
Нужно найти кратчайший путь от S до E.
Мы можем идти:
S
↓
1 шаг
↓
2 шага
↓
3 шага
...
BFS будет распространяться от S одновременно во все доступные стороны.
Как только дойдет до E — мы нашли минимальное количество шагов.
А что делать, если стартовых точек несколько?
Например, есть несколько зараженных клеток, и заражение распространяется каждую минуту, тогда мы можем положить все стартовые клетки в очередь сразу.
Это называется: Multi-Source BFS.
Именно так решается, например, задача Rotting Oranges.
Как учить BFS на практике?
Не нужно решать 30 одинаковых задач.
Лучше идти по нарастающей:
1. Binary Tree Level Order Traversal
Учимся самому BFS.
2. Shortest Path
BFS + расстояние.
3. Rotting Oranges
Multi-Source BFS.
4. Word Ladder
BFS по графу, которого напрямую вообще нет.
И вот здесь начинается самое интересное:
- в задаче с деревом граф очевиден
- в лабиринте граф — это клетки
- в Word Ladder граф — это возможные слова и переходы между ними.
То есть на более сложных задачах сначала нужно увидеть граф.
В следующих постах я детально разберу решение данных задач.