Алгоритмы. Обход в глубину (DFS) После небольшой паузы мы продолжаем разбирать различные алгоритмы. Обход в глубину (DFS) — это один из фундаментальных алгоритмов на графах, и его легче всего понять через аналогию с исследованием пещеры. Представь, что ты стоишь в системе туннелей с множеством разветвлений. Твоя стратегия заключается в том, чтобы выбрать первый попавшийся проход и идти по нему до тех пор, пока не упрешься в тупик. Только тогда ты возвращаешься назад к последнему перекрестку, где еще есть неисследованные пути, и пробуешь следующий туннель. Эта логика, где глубина проникновения важнее ширины охвата, и лежит в основе алгоритма DFS. Рассмотрим небольшой граф. Предположим, у нас есть узлы, соединенные между собой: A связан с B и C; B связан с A, D и E; C связан с A и F; D связан только с B; E связан с B и F, а F, в свою очередь, связан с C и E. Если начать обход с узла A, DFS будет двигаться следующим образом: сначала мы попадаем в A, затем углубляемся в B, оттуда — в D. Достигнув D, мы понимаем, что это тупик (сосед B уже посещен), поэтому возвращаемся обратно в B и идем по следующему пути в E. Из E переходим в F, который тоже оказывается тупиком (все соседи посещены или ведут назад). После возврата в E и затем в B, мы наконец возвращаемся в A и идем в C, но обнаруживаем, что C уже был посещен через F. Итоговый порядок посещения узлов будет таким: A, B, D, E, F, C. Граф: A / \ B C / \ \ D E F \ / (F связан с E и C) DFS от A пойдёт так: A → B → D (тупик, назад) → E → F (тупик, назад) → назад → C (уже посещён через F) Порядок посещения: A, B, D, E, F, C В этом заключается ключевое отличие DFS от другого известного алгоритма — поиска в ширину (BFS). BFS работает подобно кругам на воде: сначала исследуются все соседние узлы, затем их соседи, распространяясь равномерно во все стороны. DFS же напоминает нить Ариадны в лабиринте: он всегда идет до конца по выбранному пути и лишь затем возвращается. Граф: BFS (в ширину): DFS (в глубину): A Уровень за уровнем Ветка за веткой / \ A A B C B, C B, D, E, F, C / \ \ D, E, F D E F Для реализации DFS можно использовать два основных подхода, которые делают одно и то же, но разными средствами: рекурсию и явный стек. Рекурсивный метод полагается на стек вызовов самой программы. Когда мы пишем функцию, которая вызывает саму себя для обработки соседей, язык программирования автоматически запоминает точку возврата. Однако здесь есть важная особенность Python: не стоит задавать значение аргумента visited по умолчанию как пустое множество (set()), так как изменяемые объекты создаются один раз и будут переиспользованы во всех вызовах функции. Вместо этого нужно создавать его внутри функции, если оно не передано. Пример 1 Чтобы лучше понять, как работает рекурсия, можно проследить её выполнение по шагам. Входя в узел A, мы помечаем его как посещенный и записываем в результат. Затем смотрим на соседа B, который еще не посещен, и вызываем функцию для B. Внутри вызова для B повторяется та же логика: добавляем B в путь и идем к его первому непосещенному соседу D. В D тупик, и функция возвращает результат обратно. Далее в B очередь доходит до следующего соседа — E. Из E попадаем в F, а из F — в C. Когда все пути исчерпаны, результаты склеиваются и возвращаются наверх. Пример 2 Второй способ реализации — итеративный с использованием явного стека. Стек работает по принципу «последним пришел — первым вышел» (LIFO). Это как стопка тарелок: новую тарелку кладут сверху, и первую берут тоже сверху. В коде мы сами управляем этим стеком, помещая туда узлы для последующей обработки. Важный нюанс: чтобы порядок обхода совпадал с рекурсивной версией, соседей часто добавляют в обратном порядке. Если просто положить соседей в стек по порядку, то из-за механизма LIFO первым будет извлечен последн