Представь, что ты потерял кота в большом доме. 🐈
Есть два способа искать.
🔵 Поиск в глубину (DFS)
Ты заходишь в первую комнату.
Потом в следующую.
Потом ещё в одну.
Потом спускаешься в подвал.
Потом заходишь в кладовку.
И продолжаешь идти как можно глубже, пока путь не закончится.
Только потом возвращаешься назад и проверяешь другие комнаты.
📌 То есть принцип такой:
«Иду до конца, потом возвращаюсь.»
🟢 Поиск в ширину (BFS)
Теперь другой подход.
Сначала проверяешь все комнаты на первом этаже.
Потом все комнаты на втором.
Потом подвал.
Потом чердак.
Ты не уходишь далеко сразу.
Ты постепенно проверяешь всё, что находится рядом.
📌 Принцип такой:
«Сначала всё рядом, потом всё дальше.»
🤔 Где это используется?
🗺 Навигатор
Часто ищет кратчайший путь именно с помощью поиска в ширину (если все дороги одинаковые).
🌐 Социальные сети
Когда приложение ищет друзей друзей.
🎮 Игры
Когда персонаж ищет путь до цели.
📂 Проводник Windows
Когда нужно обойти папки и найти нужный файл.
💡 Запомнить очень легко:
🔵 Поиск в глубину — сначала идём вглубь.
🟢 Поиск в ширину — сначала проверяем всё вокруг.
Оба алгоритма делают одно и то же — обходят граф.
Но делают это совершенно по-разному.
👇 Представь лабиринт.
Как бы ты искал выход?
🟢 Сначала проверил бы все ближайшие повороты.
🔵 Или выбрал один путь и шёл бы по нему до самого конца?