Три способа построить лабиринт: DFS, Прим и Краскал

Интерактивное сравнение: https://grundyjs.ru/algorithms/maze-generation-comparison/?utm_source=rutube&utm_medium=social&utm_campaign=maze_generation_comparison&utm_content=horizontal На одинаковой сетке 9×7 с seed 34 сравниваем три рандомизированных генератора лабиринтов. Синий DFS продолжает текущую ветку, выбирая непосещённого соседа. Когда вариантов нет, возвращается по стеку. Жёлтый Прим расширяет одну связанную область: случайно выбирает стену из кандидатов и присоединяет новую клетку; устаревшие кандидаты отбрасывает. Зелёный Краскал заранее перемешивает внутренние стены и соединяет разные компоненты, пропуская стены, удаление которых создало бы цикл. У каждого результата 63 клетки и 62 прохода, без циклов: между любыми двумя клетками есть единственный путь. В этом примере тупиков у DFS — 8, у Прима — 23, у Краскала — 20. Это свойства конкретного seed, а не универсальный рейтинг алгоритмов или сложности прохождения. Равномерная выборка всех возможных лабиринтов не обещается. Одновременные фазы анимации сравнивают решения, а не скорость вычислений. В интерактивном примере можно менять размер и seed, проходить шаги, включать полный экран, делиться ссылкой на свой запуск и сохранять видео. Авторская озвучка, без музыки. #алгоритмы #лабиринт #DFS #Прим #Краскал #программирование