У меня есть задание, в котором мне нужно создать лабиринт из сетки ячеек.
Я успешно сделал это, используя Рандомизированный алгоритм Крускала, как описано на странице Wiki, с использованием непересекающихся установить структуру данных.
Теперь задание просит меня сделать то же самое, но вместо того, чтобы выбирать ячейки в случайном порядке, я просто начинаю с верхнего левого угла сетки и просматриваю все ячейки по порядку, пока не достигну внизу слева.
Модифицированный алгоритм, похоже, работает просто отлично, и я не замечаю каких-либо существенных отличий от рандомизированного алгоритма Крускала.
Итак, мой вопрос: какова важность выбора элементов в случайном порядке в рандомизированном алгоритме Крускала? Есть ли какой-нибудь лабиринт, который можно создать с помощью рандомизированной версии, но нельзя с помощью неслучайной?
Спасибо,
